分类： C/C++
2009-09-11 19:43:14
昨天我们讲解了有关递归的一些基础知识，今天我们再来看看这些递归的重大缺陷
这也是人们最容易忽视的地方，有些时候使用递归是比较简单，但却可能付出很大的负担！
相反我们可以考虑另一种形式“循环迭代”----有些时候是递归的良好替代算法！但也不尽然！
上次我们讲解了递归的使用条件----存在一个递归调用的终止条件；每次递归的调用必须
越来越靠近这个条件；只有这样递归才会终止，否则是不能使用递归的！
好了下面我们也以人们经常使用的两个例子来讲解：阶乘和菲波那契数组
我们先来看看阶乘的计算：
/
| 1 ,n<=0;
factorial(n)=|
|n*factorial(n-1) n > 0;
\
给出这种结果很容易让人考虑使用递归！
很明显这个例子符合我们前面讲的递归的使用条件，下面我们就用递归算法来实现阶乘的计算
/*使用递归来计算阶乘*/
long
factorial(int n)
{
if(n > 0)
return n * factorial(n - 1);
else
return 1;
}
我们再来一个我们自己的完全使用循环迭代来实现的方法
/*使用循环的阶乘计算方法*/
long
factorial(int n)
{
int result = 1;
while ( n > 1){
result *= n ;
n--;
}
return result;
}
对比上面这两个程序我们会发现使用迭代有一个严重的缺陷----开销太大！
每次计算参数必须压栈，为局部变量分配内存空间，寄存器的值必须保存等，
当递归调用返回是还需要还原上面的操作！所以开销是很大的，在这个计算中
相比而言我们是不会使用阶乘的！使用循环迭代无疑会带来更高的效率！
/
| 1 ,n<=1;
fibonacci(n)=| 1 ,n=2;
|fibonacci(n - 1) + fibonacci(n - 2) ,n > 0;
\
这个相信大家都不陌生了----菲波那契数组，他的定义也容易让我使用数组来解决
但稍后你将感受到你将付出多大的代价来使用这种递归！
我们来考虑一下，假设现在要计算fibonacci(n -1)和fibonacci(n -2)，请注意我们
在计算前者的时候就已经将后者计算出来了，但却无法使用，还必须重新计算！
他的代价远不止这样一个冗余的计算：每个递归调用都将触动另外两个递归调用，而这两个
当中的任何一个同样也会再触发另外两个递归调用.........
每次都会有大量的计算只被使用一次，却还要从新计算很多次。在这个例子中的开销是相当
大的！
/*利用递归计算第n 个菲波那契数*/
long
fibonacci(int n )
{
if(n <= 2)
return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
/*使用循环迭代方法完成第n个菲波那契数的计算*/
long
fibonacci(int n)
{
long result;//计算结果
long previous_first_result;//前面的一个数
long previous_second_result;//前面的第二个数
result = previous_first_result = 1;
while ( n > 2){
n--;
previous_second_result = previous_first_result;
previous_first_result = result;
result = previous_first_result + previous_second_result;
}
return result;
}
很多问题我们使用递归的形式解释，可以将问题解释的更清楚，但在实现时不一定
非要使用递归来实现，因为递归未必是最好的方法！
总之，在你使用递归来处理问题之前必须首先考虑使用递归带来的好处是否能补偿
他所带来的代价！
好了，今天就将到这了，今天这次课希望能够让大家对递归有一个更清醒的认识！
如有什么疑问可以联系我：
