斐波那契数--递归和非递归实现

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：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*）；

递归实现

function fibonacci(n){
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return arguments.callee(n-1) + arguments.callee(n-2);
    }

虽然递归实现比较好理解，代码十分简洁，但是当n比较大的时候，效率会非常低，这点不难理解，因为递归实际上是实现的是一棵树，例如f(10)：

如图可以看出递归中有许多的重复计算，所以当n比较大的时候，这个时间复杂度是呈指数增长的，效率会非常低。时间复杂度o(2^n),空间复杂度o(n);

非递归实现

一、时间复杂度为O(n)，空间复杂度为O(n)

function fibonacci(n){  
    var res = [1,1];  
    if(n == 0){  
        return 0;  
    }  
    if(n == 1 || n == 2){  
        return 1;  
    }        
    for(var i=2;i<n;i++){  
        res[i] = res[i-1] + res[i-2];  
    }  
    return res[n-1];  
}  

二、时间复杂度为O(n)，空间复杂度为O(1)

function fibonacci(n){  
    var a,b,res;  
    a = b = 1;  
    if(n == 0){  
        return 0;  
    }  
    if(n == 1 || n == 2){  
        return 1;  
    }   
    for(var i=2;i<n;i++){  
        res = a + b;  
        a = b;  
        b = res;  
    }  
    return res;  
} 

这两种非递归的方式效率在n比较大的时候将远高于递归实现方式。