Fibonacci数列F(n)递归地定义为：

         1                n<=2
F(n)={
         F(n-1)+F(n-2)     n>2

列出前几项：1，1，2，3，5，8，13，21，34。。。

    注意到这些数字没有，很多都是在大自然中出现的，我知道的少，不过你可以在互联网上搜一下，关键词：黄金分割。

没错，这个数列中体现了黄金分割，用数学方法很容易证明。首先它是发散的，但是不妨假设F(n+1)/F(n)是可以收敛的，设e=limF(n+1)/F(n)，由递推方程：F(n)=F(n-1)+F(n-2)，两边同除F(n-1)得（在极限情况下）：e=1+1/e，解出来就得e=1.618…，同时也得知它近似地相当于指数数列1.618^n，至少会以这样的增涨率增涨。

    以下总结一下Fibonacci数列的计算方法。

1，直接递归计算。

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

    它的计算效率同它的数值增涨效率一样是指数型的（O(1.618^n)），因为它会在递归中重复计算子问题，改进的方法就是‘打表’，把已经计算过的F(n)记录下来，在以后的计算中只管用就是了，也叫备忘录方法，也是DP算法的一个组成部分。

    2、备忘录方法。

int fibonacci(int n)
{
            if(mem(n)>0)
                        return mem(n);
            return mem(n)=fibonacci(n-1)+fibonacci(n-1);
}

    3. 非递归，先开一个表f(n)，然后由f(1)=f(2)=1开始计算。

inf fibonacci(int n)
{
            if(n<=2)
                        return 1;
            int *f=new int[n+1];
            f[1]=f[2]=1;
            for(int i=3;i<=n;++i)
                        f[i]=f[i-1]+f[i-2];
            int result=f[n];
            delete[] f;
            return result;
}

    前者是自顶向下，后者是自底向上，其效率是一样的，都是O(n)。从指数型复杂度到线性复杂度，是多大的提高啊。然而效率还可以提高。

4.非递归

long Fib1(int n)
{
int a,b,c;//C代表当前项，a和b分别代表当前项前面的第2项和第1项
a=b=1; //给a和b赋初值1
if(n==1||n==2)
return 1;
else
for(int i=3;i<=n;i++){
c=a+b; //求出当前项
a=b;//把前面第1项赋给前面第2项
b=c;//把当前项赋给前面第1项
}
return c;//返回所求的第n项
}