前端微专业JavaScript有一道题目是求斐波那契数列的，一开始没想很多，觉得实现功能自己已经很棒棒了（逃~~~）
后面有同学讨论直接递归特别耗费时间，开始考虑使用闭包，看我们讨论的不亦乐乎的大佬也发话了，指点我们这两种方式都不是很好，让我们去看一下尾递归(实话说，我早就还给大学老师了=。=)
言归正传，开始干活。
------------------------------假装我是分割线---------------------------
如题：
image.png
我最开始的解法是直接递归
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);
}
}
具体执行过程我后面会给传送门，我也是从那看到的。
---------------------------------分割线又来了--------------------------------
接下来我们来对比一下代码性能
直接递归的耗时：
image.png
分别比较了n为30,33,35的值时候的耗时，图中有两个数字，上面的是计算得到的斐波那契数列结果，下面是耗时，单位是毫秒。
闭包
image.png
尾递归
image.png
循环
image.png
迭代实现
//使用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;
}
从图中我们可以很明显的看出，使用尾递归计算斐波那契数列性能完胜直接递归和闭包，特别是当数值比较大的时候，尾递归的作用就越明显。循环的方式性能也很好，其实实现斐波那契数列方式多种多样，真的只是你想不到而已，好了，收工吃饭！
最后想看尾递归算法的可以看这里：尾递归实现斐波那契
网友评论