本文共 1646 字，大约阅读时间需要 5 分钟。

对于剑指offer中斐波那契数列问题进行了求解，主要使用了递归，尾递归和动态规划三种方法对问题进行了求解。分析了三种方法解决问题的优缺点。

递归方法： 多数人看到题目的第一想法就是使用递归方法，因为转移关系显而易见，即f(n)=f(n-1)+f(n-2)

int Fibonacci(int n) {
          	if(n<=1)        return n;    n=Fibonacci(n-1)+Fibonacci(n-2)	 return n;    }

但是如果n很大的话很容易造成递归栈溢出。

我们来看一下这个递归算法的复杂度：每次基本运算次数为1，总的运算次数是个等比数列，即第一次需要计算f(n-1)和f(n-2)，第二次需要计算f(n-2)、f(n-3)和f(n-3)、f(n-4)。。。一直到f(1)，总共n次，所以总的运算次数是以1为首项,2为公比，次数为n的等比数列求和，所以时间复杂度为2的n次方。 不光时间复杂度大，空间复杂度同样大。递归算法有个问题在于，在下一层递归完成返回值之前，本层函数依然在等待，n层递归就意味着有n个函数在运行，这需要在栈中开辟大量的空间。计算机给每个线程分配的空间是有限的，一般为1-8M，遇到递归次数很大的时候就会超出这个范围，造成栈溢出。 而在本题中，测试范例中显然有个极大的n，使用递归会造成栈溢出。此外，我们注意到计算的时候出现了重复计算，所以需要对此进行优化。 尾递归方法： 如果把递归过程看做二叉树的遍历，那么递归就是从上到下，而尾递归则是从下到上，每层运行完该层就被释放，计算结果通过函数参数传递，不会一直占用空间。时间复杂度为n。此外，f(n-1)是由f(n-2)得到，而不像是递归中分别得到，减少了重复计算。

int f(int n,int first,int second)    {
           if(n<=0)            return 0;        if(n==1||n==2)            return second;        return f(n-1,second,first+second);    }        int Fibonacci(int n) {
           	 return f(n,1,1);    }

在编译器检测到尾递归时，新函数会覆盖在原函数的栈空间上，没有分配新的内存，所以空间复杂度为O(1)。

动态规划方法： 使用循环可以很好的解决递归中内存一直占用的问题。 求数列第n项只与前两项有关，那么每次只需要关心前两项即可。这也就将大问题分解成了很多个小问题，求得每次最优解最后就得到了总的最优解。这也就是动态规划。

int Fibonacci(int n) {
          	if(n<=1)        return n;    vector
   
     dp(n+1,1);        dp[0]=0;    for(int i=2;i<=n;i++)	    dp[i]=dp[i-1]+dp[i-2];	 return dp[n];    }
   

注意到实际上不需要申请n个空间，每次 dp[i]只与dp[i-1]和dp[i-2]有关，所以我们只需要三个变量即可。

int Fibonacci(int n) {
      if(n<=0)        return 0;   if(n<=2)        return 1;    int first=1,second=1,sum;    for(int i=2;i

总结，递归类似于二叉树的中后序遍历，从上往下需要计算每个节点的值，时间复杂度为O(2^n)，空间复杂度为O(n)。尾递归类似于二叉树的层次遍历，从下往上计算不需要保存之前的值。动态规划和尾递归都是O(n)的时间复杂度和O(1)的空间复杂度，都避免了重复计算。

转载地址：http://lndmi.baihongyu.com/