前端微專業(yè)JavaScript有一道題目是求斐波那契數(shù)列的沼撕，一開始沒想很多渔隶，覺得實(shí)現(xiàn)功能自己已經(jīng)很棒棒了（逃~~~）
后面有同學(xué)討論直接遞歸特別耗費(fèi)時(shí)間御蒲，開始考慮使用閉包，看我們討論的不亦樂乎的大佬也發(fā)話了平委，指點(diǎn)我們這兩種方式都不是很好，讓我們?nèi)タ匆幌挛策f歸(實(shí)話說夺谁，我早就還給大學(xué)老師了=廉赔。=)
言歸正傳，開始干活匾鸥。
------------------------------假裝我是分割線---------------------------
如題：
我最開始的解法是直接遞歸
function sum(n){
if(n==0){
return 0;
}else if(n==1) {
return 1;
}
else{
return (arguments.callee(n-1)+arguments.callee(n-2));
}
}
這個(gè)實(shí)現(xiàn)簡(jiǎn)單明了就是執(zhí)行速度太慢了蜡塌，因?yàn)榫幾g器是以如下方式進(jìn)行計(jì)算的（例如計(jì)算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)都被計(jì)算了2次，而且遞歸函數(shù)以2的指數(shù)增長(zhǎng)勿负。所以當(dāng)計(jì)算到30時(shí)就變得非常慢馏艾。(當(dāng)然這都是后話了，我開始哪里知道這么多~)
后來群里同學(xué)說使用閉包會(huì)比直接遞歸快奴愉，那我就試著用了下閉包琅摩；
var sum =(function (){
return function(n){
if(n==0 || n==1){
return n;
}else{
return (sum(n-1)+sum(n-2));
}
}})();
使用了閉包確實(shí)感覺自己吊了一點(diǎn)啊，整個(gè)人都萌萌噠锭硼，而且后面測(cè)試速度也證實(shí)了比我原來的好一點(diǎn)房资。
后面， 大佬指導(dǎo)說直接遞歸和閉包都很影響性能（我實(shí)現(xiàn)出來都很不容易呀）檀头，告訴我們使用尾遞歸會(huì)極大的提高性能轰异，好吧，我只好去查查什么是尾遞歸了暑始，看了幾個(gè)demo我寫了如下代碼：
function sum(n,a,b){
if (n ==0 ){
return a;
}
else{
return sum(n-1, b, a +b);
}
}
具體執(zhí)行過程我后面會(huì)給傳送門溉浙，我也是從那看到的。
---------------------------------分割線又來了--------------------------------
接下來我們來對(duì)比一下代碼性能
直接遞歸的耗時(shí)：
分別比較了n為30,33,35的值時(shí)候的耗時(shí)蒋荚，圖中有兩個(gè)數(shù)字戳稽，上面的是計(jì)算得到的斐波那契數(shù)列結(jié)果，下面是耗時(shí)，單位是毫秒惊奇。
閉包
尾遞歸
循環(huán)
迭代實(shí)現(xiàn)
//使用Java方式互躬，主要是看實(shí)現(xiàn)思想
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;
}
從圖中我們可以很明顯的看出，使用尾遞歸計(jì)算斐波那契數(shù)列性能完勝直接遞歸和閉包颂郎，特別是當(dāng)數(shù)值比較大的時(shí)候吼渡，尾遞歸的作用就越明顯。循環(huán)的方式性能也很好乓序，其實(shí)實(shí)現(xiàn)斐波那契數(shù)列方式多種多樣寺酪，真的只是你想不到而已，好了替劈，收工吃飯寄雀！
最后想看尾遞歸算法的可以看這里：尾遞歸實(shí)現(xiàn)斐波那契
