斐波那契数列（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比较大的时候将远高于递归实现方式。
