斐波那契数列引发的思索

[Sphinm]

前端微专业JavaScript有一道题目是求斐波那契数列的，一开始没想很多，觉得实现功能自己已经很棒棒了。后面有同学讨论直接递归特别耗费时间，开始考虑使用闭包，看我们讨论的不亦乐乎的大佬也发话了，指点我们这两种方式都不是很好，让我们去看一下尾递归(实话说，我早就还给大学老师了=。=)
言归正传，开始干活。

---

更新一下

采用循环方法，复杂度为 o(n)

var arr = [];
for (var i = 0; i < 10; i++) {
    i <= 1 ? arr.push(1) : arr.push(arr[i - 1] + arr[i - 2]);
}
console.log(arr)
// [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

------------------------------假装我是分割线---------------------------
如题：

我最开始的解法是直接递归

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

这个实现简单明了就是执行速度太慢了，因为编译器是以如下方式进行计算的（例如计算Fib（6））：

Fib(6) = Fib(5) + Fib(4);
         = Fib(4) + Fib(3) + Fib(3) + Fib(2);
         = Fib(3) + Fib(2) + Fib(2) + Fib(1) + Fib(2) + Fib(1) + Fib(2);
         = Fib(2) + Fib(1) + Fib(2) + Fib(2) + Fib(1) + Fib(2) + Fib(1) + Fib(2);
         = 8

从上面的递归展开式可以看出Fib(4),Fib(3)都被计算了2次，而且递归函数以2的指数增长。所以当计算到30时就变得非常慢。(当然这都是后话了，我开始哪里知道这么多~)

后来群里同学说使用闭包会比直接递归快，那我就试着用了下闭包；

var sum = (function() {
    return function(n) {
        if (n == 0 || n == 1) {
            return n;
        } else {
            return (sum(n - 1) + sum(n - 2));
        }
    }
})();

使用了闭包确实感觉自己吊了一点啊，整个人都萌萌哒，而且后面测试速度也证实了比我原来的好一点。

后面， 大佬指导说直接递归和闭包都很影响性能（我实现出来都很不容易呀），告诉我们使用尾递归会极大的提高性能，好吧，我只好去查查什么是尾递归了，看了几个demo我写了如下代码：

function sum(n, a, b) {
    if (n == 0) {
        return a;
    } else {
        return sum(n - 1, b, a + b);
    }
}

具体执行过程我后面会给传送门，我也是从那看到的。

---------------------------------分割线又来了--------------------------------

接下来我们来对比一下代码性能

直接递归的耗时：

分别比较了n为30,33,35的值时候的耗时，图中有两个数字，上面的是计算得到的斐波那契数列结果，下面是耗时，单位是毫秒。

闭包

尾递归

循环

迭代实现

//使用Java方式，主要是看实现**
public static long fibo3(long n){    
    if(n<2) return n;    
    long pre=1,prepre=1,ret=0;    
    for(int i=2;i<n;i++){    
        ret=pre+prepre;    
        prepre=pre;    
        pre=ret;    
    }    
    return ret;    
}  

从图中我们可以很明显的看出，使用尾递归计算斐波那契数列性能完胜直接递归和闭包，特别是当数值比较大的时候，尾递归的作用就越明显。循环的方式性能也很好，其实实现斐波那契数列方式多种多样，真的只是你想不到而已，好了，收工吃饭！

最后想看尾递归算法的可以看这里：尾递归实现斐波那契