警惕递归

时间：2009-07-15 来源：litary1986

警惕递归
递归是一种解决复杂问题的有效算法，函数通过简化问题求解过程，将被简化的问题再交给一个或
多个与自己完成一样的函数，从而让程序解决这个问题。比如说汉诺塔问题。
递归算法思路清晰，编成代码简单优美，缺点是会消耗不少的栈空间，甚至有时候会带来额外的开销。

递归所对应的另一种算法是迭代（也就是循环），相应的，迭代的优点是效率高，但是程序可读性方面没有
递归好。大部分递归都可以方便的用迭代来取代，因此我建议如果递归不是很复杂，还是用循环来替代。

    我们用最简单常见的阶乘算法和斐波纳契数列来说明：
阶乘递归程序：
long factorial(int n){
static int time = 0; //for debug
if(3==n) cout << "f(3) time: " << ++time << endl; //for debug
if(n<=1) return 1;
return n*factorial(n-1);
}
阶乘迭代程序
long factorial(int n){
long result = 1;
while(n>1){
  result *= n;
  n--;
}
return result;
}
为了测试factorial（3）在n很大时候被调用的次数，我在程序里加了2句计数的代码，
static int time = 0; //for debug
if(3==n) cout << "f(3) time: " << ++time << endl; //for debug
然后我们调用递归的factorial(10)；factorial(20)；factorial(30)；
发现最后都是出现f(3) time: 1，说明随着n的增长，只有栈的消耗，没有其他额外的开销，
这里基本用递归还是迭代差别不大。

斐波纳契数列递归程序
long fibonacci(int n){
static int time = 0; //for debug
if(3==n) cout << "f(3) time: " << ++time << endl;
if(n<=2) return 1;
return fibonacci(n-2)+fibonacci(n-1);
}
斐波纳契数列迭代程序
long fibonacci(int n){
long result = 1;
long now = 1;
long next = 1;
while(n>2){
  result = now + next;
  now = next;
  next = result;
  n--;
}
return result;
}
然后我们调用递归的fibonacci(10)；fibonacci(20)；fibonacci(30)；
发现依次出现：f(3) time: 21，f(3) time: 2584，f(3) time: 317811，
大家可以看到，调用递归的fibonacci(30)的时候，fibonacci（3）被执行的次数达到了恐怖的317811次！
在我电脑上是跑了好久才出结果的，所以大家要小心递归这种额外的开销，当一个递归里出现分解调用
同一个函数（参数不同）两次以上的情况，一定要谨慎使用。