遞歸應(yīng)該是眾所周知的概念，而且我們遇到次數(shù)最多的例子可能就是斐波那契數(shù)列了，規(guī)則如下：

f(n)=f(n-1)+f(n-2),
    for n=2,3,4,...n and 
        f(0)=0 and f(1)=1

一個(gè)斐波那契數(shù)列數(shù)列是前面兩個(gè)斐波那契數(shù)的加和。
所以我們一般寫的代碼可能就是這樣的：

function fibonacci(n) {
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

問題引入

如果稍微了解一點(diǎn)數(shù)據(jù)結(jié)構(gòu)應(yīng)該知道入棧、出棧、堆棧等等這些概念，所以這個(gè)遞歸的過程其實(shí)是把中間值壓入到了內(nèi)存的一個(gè)棧中，并且保持到終止條件滿足。

拿這個(gè)斐波那契數(shù)列當(dāng)例子有點(diǎn)令人費(fèi)解，這里拿階乘說明吧，階乘代碼如下：

function factorial(n){
    return n==1?1:n*factorial(n-1);
}

稍微改動(dòng)下代碼，記錄它的計(jì)算過程：

function factorial(n) {
    var re;
    re = n == 1 ? 1 : n * factorial(n - 1);
    console.log(re);
    return re;
}
factorial(5);

打印出的計(jì)算過程

這下應(yīng)該可以比較清楚地看出對(duì)于中間值是先壓入棧中保存，最后再一個(gè)個(gè)出棧，并且符合堆棧中“后入先出”的原則。

再回到斐波那契數(shù)列，每次迭代過程中都會(huì)計(jì)算兩個(gè)函數(shù)，比如f(9)會(huì)計(jì)算f(8)+f(7)，求f(8)的時(shí)候又要計(jì)算f(7)+f(6),顯然中間有了較多的重復(fù)計(jì)算，這太浪費(fèi)內(nèi)存、白白消耗cpu了，所以如果想要減少重復(fù)復(fù)雜的、CPU消耗大的計(jì)算，很有必要來優(yōu)化下我們的代碼。

解決方案

使用計(jì)算緩存(Memoization)來緩存復(fù)雜計(jì)算的結(jié)果。上個(gè)例子：

var fibonacci = function() {
    var memo = [0, 1];
    var fib = function(n) {
        var result = memo[n];
        if (typeof result != "number") {
            result = fib(n - 1) + fib(n - 2);
            memo[n] = result;
        }
        return result;
    }
    return fib;
}();

也就是我們使用數(shù)組緩存中間值，而不再重新創(chuàng)建他們，從而縮減了迭代和計(jì)算的次數(shù)。尤其對(duì)于斐波那契數(shù)列和階乘這種都會(huì)使用前面值的計(jì)算效果尤其好。趕緊來驗(yàn)證下：

var fibonacci = function() {
    var memo = [0, 1];
    var fib = function(n) {
        var result = memo[n];
        if (typeof result != "number") {
            result = fib(n - 1) + fib(n - 2);
            memo[n] = result;
        }
        return result;
    }
    return fib;
}();
console.time("memo");
for(var i=0;i<15;i++){
    fibonacci(i);
}
console.timeEnd("memo");

var fibon = function(n) {
    return n < 2 ? n : fibon(n - 1) + fibon(n - 2);
}
console.time("non-memo");
for(var i=0;i<15;i++){
    fibon(i);
}
console.timeEnd("non-memo");

結(jié)果是：

memo: 0.158ms
non-memo: 0.458ms

雖然這樣的例子顯示結(jié)果良好，但是更多時(shí)候我們也就計(jì)算數(shù)列的某一個(gè)值，如果數(shù)字較小，那么往數(shù)組中存儲(chǔ)數(shù)據(jù)的過程的時(shí)間消耗就會(huì)比較明顯了，此時(shí)使用緩存會(huì)顯得是個(gè)累贅。但是使用緩存的優(yōu)勢(shì)在遞歸次數(shù)越大的時(shí)候是會(huì)越明顯滴~

//這是我只計(jì)算斐波那契數(shù)列第30個(gè)值時(shí)兩者的運(yùn)行時(shí)間：
memo: 0.171ms
non-memo: 13.369ms

當(dāng)我想看看計(jì)算數(shù)列第50個(gè)值時(shí)運(yùn)用緩存到底運(yùn)行時(shí)間能差多少，瀏覽器竟然給我都罷工了。。。

Underscore.js庫(kù)有提供實(shí)現(xiàn)該功能的memoize()函數(shù)。使用方法如下：

var fibonacci = _.memoize(function(n) {
  return n < 2 ? n: fibonacci(n - 1) + fibonacci(n - 2);
});

對(duì)于耗時(shí)計(jì)算計(jì)算較長(zhǎng)的計(jì)算，強(qiáng)烈推薦使用哦~