题目：斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……。在数学上，斐波纳契数列以如下被以递归的方法定义：
F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n≥2，n∈N*）
源码(递归算法)：
long Fibonacci(long n) //递归算法 { if(n<=1) return n; //终止递归的条件 else return Fibonacci(n-1) + Fibonacci(n-2);//递归步骤 }
分析：
这个Fibonacci的递归实现，每次递归调用都触发另外两个递归，而这两个递归在调用的时候每个都还要触发两外的两个递归调用，再接下去的调用也是如此。现在，我们知道，这个冗余的递归调用是以几何级数增长的。例如，在递归计算Fibonacci(10)时，Fibonacci(3)的值被计算了21次。而在递归计算Fibonacci(30)，这个调用的次数是骇人的317811次！这些个计算实际上只有一次是必要的，其余的纯属浪费！
下面的程序使用一个简单循环迭代来代替递归，这个非递归的形式不如上文给出的递归简单，也不太符合Fibonacci的递归定义，但是，它的效率提高了几十万倍！
源码(非递归/迭代算法)：
//计算斐波那契数列的非递归算法(迭代) long Fibonacci(long n) { int i; if(n<=1) return n; //Fib(0)或Fib(1)的情况 long FibCurrent , FibTwoBack = 0 , FibOneBeck = 1; //用数组保存程序更简洁，但不能明显的看出迭代的思想 for(i=2 ; i<=n ; i++) //n≥2的情况 { FibCurrent = FibOneBeck + FibTwoBack; //计算Fib(i)=Fib(i-1)+Fib(i-2) /* 下面的保存顺序不能对调 */ FibTwoBack = FibOneBeck; //保存Fib(i-1)作为下趟的Fib(i-2) FibOneBeck = FibCurrent; //保存Fib(i)作为下趟的Fib(i-1) } return FibCurrent; }
所以，本文的结论就是，当你使用递归实现一个函数之前，先问问自己使用递归的好处是否抵得上它所要付出的代价。当然，编程的时候，无论什么实现方式，我们都应该问问自己这个问题。
原文：http://www.cnblogs.com/eniac12/p/4841320.html