斐波那契数列（Fibonaccisequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（LeonardodaFibonacci[1]）以兔子繁殖为例子而引入，故又称为“兔子数列”。指的是这样一个数列：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*）#include<iostream>usingnamespacestd;//递归形式//longlongfibonacci(inti)//{//returni<2?i:fibonacci(i-1)+fibonacci(i-2);//}voidtest1(){cout<<fibonacci(6)<<endl;;}//非递归形式longlongfibonacci(intn){inttem[2];tem[0]=1;tem[1]=1;if(n==0){return0;}if(n==1){return1;}else{for(inti=2;i<n;i++){inttemp=tem[0]+tem[1];tem[1]=tem[0];tem[0]=temp;}returntem[0];}}//优化时间复杂度O（n）longlongfibonacci(intn){longlongfibonacci[3]={0,1,n};for(inti=2;i<=n;++i){fibonacci[2]=fibonacci[1]+fibonacci[0];fibonacci[0]=fibonacci[1];fibonacci[1]=fibonacci[2];}returnfibonacci[2];}intmain(){test1();system("pause");return0;}

我们不难发现在这棵树中有很多结点会重复的，而且重复的结点数会随着n的增大而急剧增加。这意味这计算量会随着n的增大而急剧增大。事实上，用递归方法计算的时间复杂度是以n的指数的方式递增的.

在分析算法的时间复杂度的时候，我们也可以得到相同的结果，非递归使用的是for循环，其时间复杂度为O(n)。而递归的时间复杂度则比较复杂，其分析出来为O(2^n)。

这里需要说明的就是，非递归的for循环其时间复杂度O(n)虽然很小，但是其空间复杂度缺比递归调用差得多。因为，for循环在每次循环的时候，都把相应的数值保存下来了，而递归调用却不会保存相应的数值。