斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列、因數(shù)學(xué)家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入惊橱，故又稱為“兔子數(shù)列”局荚，指的是這樣一個數(shù)列：1、1钞澳、2怠惶、3、5轧粟、8策治、13脓魏、21、34通惫、……在數(shù)學(xué)上茂翔，斐波納契數(shù)列以如下被以遞歸的方法定義：F(0)=0，F(xiàn)(1)=1, F(n)=F(n-1)+F(n-2)（n>=2履腋，n∈N*）珊燎；
遞歸實現(xiàn)
function fibonacci(n){
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return arguments.callee(n-1) + arguments.callee(n-2);
}
雖然遞歸實現(xiàn)比較好理解，代碼十分簡潔府树，但是當n比較大的時候俐末，效率會非常低，這點不難理解奄侠，因為遞歸實際上是實現(xiàn)的是一棵樹卓箫，例如f(10)：
如圖可以看出遞歸中有許多的重復(fù)計算，所以當n比較大的時候垄潮，這個時間復(fù)雜度是呈指數(shù)增長的烹卒，效率會非常低。時間復(fù)雜度o(2^n),空間復(fù)雜度o(n);
非遞歸實現(xiàn)
一弯洗、時間復(fù)雜度為O(n)旅急，空間復(fù)雜度為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];
}
二、時間復(fù)雜度為O(n)牡整，空間復(fù)雜度為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比較大的時候?qū)⑦h高于遞歸實現(xiàn)方式藐吮。
