先看代碼:

function fib(n){
    if(n===1){
        return 1;
    }
    if(n===2){
        return 1;
    }
    if(n>2){
        return fib(n-1)+fib(n-2);
    }
}
console.log(fib(11));

這是一個(gè)很典型的利用遞歸計(jì)算斐波那契數(shù)列。

遞歸的缺點(diǎn)也是顯而易見(jiàn)的,我們計(jì)算fib(6)時(shí) 要計(jì)算fib(5)和fib(4)

而后計(jì)算fib(7)時(shí),又要重復(fù)計(jì)算fib(6)與fib(5)

很明顯,我們之前已經(jīng)計(jì)算過(guò)了fib(6)與fib(5),現(xiàn)在重復(fù)計(jì)算,造成了浪費(fèi).

首先我們來(lái)觀察一下 當(dāng)n從20到21時(shí),調(diào)用此函數(shù) 內(nèi)部會(huì)多調(diào)用多少次此函數(shù)?

var count=0;//計(jì)數(shù)器
function fib(n){
    count++;
    if(n===1){
        return 1;
    }
    if(n===2){
        return 1;
    }
    if(n>2){
        return fib(n-1)+fib(n-2);
    }
}
console.log(fib(20));
console.log(count);//13529次
count = 0;
console.log(fib(21));
console.log(count);//21891次  從20到21 調(diào)用次數(shù)增加不少

其實(shí)我們完全可以將之前計(jì)算過(guò)的數(shù)值用一個(gè)數(shù)組保存起來(lái)，如果需要重復(fù)計(jì)算，先去數(shù)組內(nèi)部查找，如果數(shù)組里面存在該結(jié)果，直接return

var cache = [0,1,1];
function fib(n){
    if(n<=2){
        return cache[n];
    }else{
        if(cache[n]){ //如果緩存數(shù)組中存在 直接返回
            return cache[n];
        }else{
            var temp = fib(n-1)+fib(n-2); //如果緩存數(shù)組中不存在 進(jìn)行遞歸
            cache[n]=temp;   //將遞歸結(jié)果存入緩存數(shù)組
            return temp;
        }
    }
 }

這樣已經(jīng)能夠節(jié)省很多遞歸造成的空間浪費(fèi)了。

但是緩存數(shù)組孤零零的放在全局作用域，不夠安全，封裝性也不好，比較寂寞。

我們希望他們聯(lián)系的能夠更緊密一些，就像一個(gè)整體。

于是有了下面的代碼：

var fib = (function(){
    var cache = [0,1,1];
    var fib = function() {
        if(n<=2){
            return cache[n];
        }else{
            if(cache[n]){ //如果緩存數(shù)組中存在 直接返回
                return cache[n];
            }else{
                var temp = fib(n-1)+fib(n-2); //如果緩存數(shù)組中不存在 進(jìn)行遞歸
                cache[n]=temp;   //將遞歸結(jié)果存入緩存數(shù)組
                return temp;
            }
        }
    }
    return fib;
})()

這樣，我們通過(guò)閉包，只能通過(guò)返回的fib方法對(duì)cache進(jìn)行操作了。

當(dāng)然，你也可以像下面這樣寫(xiě)：

function createCache(){
    var cache=[0,1,1];//緩存數(shù)組被封裝在閉包中,外界只能通過(guò)返回的方法進(jìn)行操作
    return function editCache(index,value){
        if(value==undefined){
            return cache[index];
        }else{
            cache[index]=value;
        }
    }
 }

 var fibCache=createCache();//創(chuàng)建緩存數(shù)組并且獲取接口方法

 function fib(n){
    if(n<=2){
        return fibCache(n);
    }else{
        if(fibCache(n)){
            return fibCache(n);
        }else{
            var temp = fib(n-1)+fib(n-2);
            fibCache(n,temp);
            return temp;
        }
    }
 }

遞歸效率低是函數(shù)調(diào)用的開(kāi)銷導(dǎo)致的。

在一個(gè)函數(shù)調(diào)用之前需要做許多工作，比如準(zhǔn)備函數(shù)內(nèi)局部變量使用的空間、搞定函數(shù)的參數(shù)等等，這些事情每次調(diào)用函數(shù)都需要做，因此會(huì)產(chǎn)生額外開(kāi)銷導(dǎo)致遞歸效率偏低 來(lái)自知乎

其實(shí)一般遞歸的方法我們都可以通過(guò)迭代的方式來(lái)做，for循環(huán)就是一個(gè)很好的選擇：

function fib(n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    var arr = [0,1,1];
    for(var i = 2; i <= n; i++) {
        arr[i] = arr[i-1] + arr[i-2];
    }
    return arr[n];
}

看起來(lái)也挺好的，是吧。

下面進(jìn)入算法時(shí)間，題目來(lái)自《劍指Offer》，當(dāng)然，遞歸依然是主角。

題目一：
一只青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上 2 級(jí)。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法？

解題：數(shù)學(xué)歸納法。
1級(jí)臺(tái)階，1種跳法，直接跳上1級(jí)臺(tái)階 f(1) = 1；

2級(jí)臺(tái)階，2種跳法，直接跳上2級(jí)臺(tái)階或者連續(xù)跳兩次，每次一級(jí) f(2) = 2；

3級(jí)臺(tái)階，如果第一次跳1級(jí)，剩下2級(jí)臺(tái)階，f(2) = 2種跳法;如果第一次跳2級(jí)，剩下1級(jí)臺(tái)階，f(1) = 1種跳法。f(3) = f(2) + f(1) = 2 + 1 = 3；

4級(jí)臺(tái)階，如果第一次跳1級(jí)，剩下3級(jí)臺(tái)階，由上一條可知有3種跳法；如果第一次跳2級(jí)，剩下2級(jí)臺(tái)階，由上上條可知有2種跳法，f(4) = f(3) + f(2) = 3 + 2 = 5；

n級(jí)臺(tái)階，f(n) = f(n-1) + f(n-2)

很熟悉對(duì)嗎？

function jump(n) {
    if (n <= 0) {
        return;
    } else if (n > 0 && n <= 2) {
        return n;
    } else if (n > 2) {
        return jump(n-1) + jump(n-2);
    }
}

題目二：
一只青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上 2 級(jí)……它也可以跳上 n 級(jí)。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法？

解題：繼續(xù)歸納。
1級(jí)臺(tái)階，1種跳法

2級(jí)臺(tái)階，2種跳法

3級(jí)臺(tái)階，4種跳法 f(3) = f(2) + f(1) + 1 = 4

4級(jí)臺(tái)階，第一次跳1級(jí)，后面有f(3)種跳法，第一次跳2級(jí)，后面有f(2)種跳法，第一次跳3級(jí)，后面有f(1)種跳法，第一次跳4級(jí)，沒(méi)了
總共f(4) = f(3) + f(2) + f(1) + 1 = 8種跳法

5級(jí)臺(tái)階，f(5) = f(4) + f(3) + f(2) + f(1) + 1 = 16種跳法

歸納得，f(n) = f(n-1) + f(n-2) + ... + f(1) + 1

function jump(n) {
    if (n <= 0) {
        return;
    } else if (n > 0 && n <= 2) {
        return n;
    } else if (n > 2) {
        var tmp = 0;
        while(number > 1){
            tmp+=jump(n-1);
            number--;
        }
        return tmp+1;
    }
}