這兩天搜了下JS遞歸的相關(guān)文章， 覺(jué)得這篇文章很不錯(cuò)， 就順手翻譯了下，也算給自己做個(gè)筆記，題目是我自己加的。原文很長(zhǎng)，寫(xiě)得也很詳盡，這里并非逐字翻譯， 而是作者所講的主要概念加上我自己的一些理解，本文中解決方案的實(shí)際意義并不是特別大，但算法的邏輯挺有意思，不過(guò)也略抽象，理解需要花點(diǎn)時(shí)間（囧，估計(jì)我太閑了） 文中的用例?全部來(lái)自原文：

原文鏈接：（原題為：理解JS函數(shù)式編程中的遞歸）
Understanding recursion in functional JavaScript programming

在JS的遞歸調(diào)用中，JS引擎將為每次遞歸開(kāi)辟一段內(nèi)存用以?xún)?chǔ)存遞歸截止前的數(shù)據(jù)，這些內(nèi)存的數(shù)據(jù)結(jié)構(gòu)以“棧”的形式存儲(chǔ)，這種方式開(kāi)銷(xiāo)非常大，并且一般瀏覽器可用的內(nèi)存非常有限。
下面這個(gè)函數(shù)使用遞歸的方式求和：

//使用遞歸將求和過(guò)程復(fù)雜化
function sum(x, y) {
    if (y > 0) {
      return sum(x + 1, y - 1);
    } else {
      return x;
    }
}

sum(1, 10); // => 11

當(dāng)運(yùn)算規(guī)模較小時(shí)，這種方式可以正常輸出結(jié)果，可是當(dāng)把參數(shù)變?yōu)閟um(1,100000)時(shí)，就會(huì)造成“棧溢出錯(cuò)誤（stack overflow 這可不是那個(gè)問(wèn)答網(wǎng)站哦）”瀏覽器就會(huì)報(bào)錯(cuò)Uncaught RangeError: Maximum call stack size exceeded

在有些語(yǔ)言中，執(zhí)行尾遞歸時(shí)將會(huì)被自動(dòng)識(shí)別，繼而在運(yùn)行時(shí)優(yōu)化成循環(huán)的形式，這種優(yōu)化邏輯大多是Tail Call Optimisation尾部調(diào)用優(yōu)化，（尾調(diào)用概念就是在函數(shù)最后一步調(diào)用其他函數(shù)，尾遞歸即在最后一步調(diào)用自身）關(guān)于尾遞歸與尾調(diào)優(yōu)化更詳細(xì)的概念解讀可以看下阮一峰的這篇文章? 尾調(diào)用優(yōu)化 （也就是說(shuō)執(zhí)行尾遞歸時(shí)，程序無(wú)須儲(chǔ)存之前調(diào)用棧的值，直接在最后一次遞歸中輸出函數(shù)運(yùn)算結(jié)果，這樣就大大節(jié)省了內(nèi)存，而這種優(yōu)化邏輯就是在代碼執(zhí)行的時(shí)候?qū)⑵滢D(zhuǎn)換為循環(huán)的形式）
另外在Babel的說(shuō)明文檔中也提到了尾調(diào)用? BABEL Tail Calls

以上的sum函數(shù)， 使用尾遞歸，將是這個(gè)樣子：

function sum(x, y) {
    function recur(a, b) {
        if (b > 0) {
            return recur(a + 1, b - 1);
        } else {
            return a;
        }
    }
//尾遞歸即在程序尾部調(diào)用自身，注意這里沒(méi)有其他的運(yùn)算
    return recur(x, y);
}

sum(1, 10); // => 11

以上這種寫(xiě)法在有TCO機(jī)制的語(yǔ)言中將在執(zhí)行時(shí)內(nèi)部?jī)?yōu)化成循環(huán)形式而不會(huì)產(chǎn)生“棧溢出”錯(cuò)誤，注意，在當(dāng)前版本的JS中以上寫(xiě)法是無(wú)效的！因?yàn)樵诋?dāng)前普遍的JS版本（ES5）中并沒(méi)有這個(gè)優(yōu)化機(jī)制。但是在ES6中已經(jīng)實(shí)現(xiàn)了這個(gè)機(jī)制 在當(dāng)前普遍的JS版本中我們只能使用替代方案。

這里插一句：使用Babel可以在當(dāng)前JS版本中用ES6的特性（Babel可以將使用ES6特性編程的代碼轉(zhuǎn)換成兼容的ES5形式），將原sum()函數(shù)輸入Babel的編譯器后，確實(shí)被轉(zhuǎn)換成了循環(huán)的形式，感興趣的同學(xué)可以自己試試：
BABEL編譯器轉(zhuǎn)換sum()函數(shù)的結(jié)果如下（對(duì)于算法邏輯不太感興趣的同學(xué)看到這里就差不多了，
可以直接將一些深遞歸放到Babel中轉(zhuǎn)換下就可以了）：
var _again = true;

  _function: while (_again) {
    var x = _x,
        y = _x2;
    _again = false;

    if (y > 0) {
      _x = x + 1;
      _x2 = y - 1;
      _again = true;
      continue _function;
    } else {
      return x;
    }   } } 

在當(dāng)前的JS版本（ES5）中可以使用以下方式來(lái)優(yōu)化遞歸。
我們可以定義一個(gè)Trampolining（蹦床）函數(shù)來(lái)解決參數(shù)過(guò)大造成的“棧溢出”問(wèn)題。

    //放入trampoline中的函數(shù)將被轉(zhuǎn)換為函數(shù)的輸出結(jié)果
function trampoline(f) {
    while (f && f instanceof Function) {
        f = f();
    }
    return f;
}

function sum(x, y) {
    function recur(x, y) {
        if (y > 0) {
          return recur.bind(null, x + 1, y - 1);
        } else {
          return x;
        }
    }
//
    return trampoline(recur.bind(null, x, y));
}

sum(1, 10); // => 11

在以上的方案中， trampoline函數(shù)接受一個(gè)函數(shù)作為參數(shù)，如果參數(shù)是函數(shù)就被執(zhí)行后返回，如果參數(shù)不是函數(shù)將被直接返回，嵌套函數(shù)recur中，當(dāng)y>0時(shí)返回一個(gè)參數(shù)更新了的函數(shù)，這個(gè)函數(shù)被轉(zhuǎn)入trampoline中循環(huán)，直到recur返回x，x不是函數(shù)于是在trampoline中被直接返回。原文中作者對(duì)于每一步都有詳盡的解釋?zhuān)?感興趣的同學(xué)建議可以去看看原文。簡(jiǎn)單地說(shuō)：以上邏輯就是將遞歸變成一個(gè)條件， 而外層trampoline函數(shù)執(zhí)行這個(gè)條件判斷并循環(huán)。好吧，接下來(lái)更繞的來(lái)了-_-#

以上這種方法雖然解決了大參數(shù)遞歸的問(wèn)題，但是卻需要將代碼轉(zhuǎn)換成trampoline的模式，比較不靈活， 下面作者介紹了一種更靈活方便的方案。

作者在此警告：前方高能， 該方法不需要改動(dòng)源碼，但是略抽象，理解可能需要花點(diǎn)時(shí)間。

function tco(f) {
    var value;
    var active = false;
    var accumulated = [];

    return function accumulator() {
        accumulated.push(arguments);

        if (!active) {
            active = true;

            while (accumulated.length) {
                value = f.apply(this, accumulated.shift());
            }

            active = false;

            return value;
        }
    }
}
//這種方式確實(shí)有點(diǎn)奇怪，但的確沒(méi)有改動(dòng)很多源碼，只是以直接量的形式使用tco函數(shù)包裹源碼
var sum = tco(function(x, y) {
    if (y > 0) {
      return sum(x + 1, y - 1)
    }
    else {
      return x
    }
});
sum(1, 10) // => 11
sum(1, 100000) // => 100001 沒(méi)有造成棧溢出

首先以函數(shù)表達(dá)式的形式將tco函數(shù)的返回值賦給sum，tco函數(shù)的返回值是accumulator函數(shù)，也就是說(shuō)當(dāng)執(zhí)行sum(1,10)的時(shí)候即是在執(zhí)行accumulator(1,10)，牢記這點(diǎn)對(duì)后續(xù)理解很有幫助。

accumulator是個(gè)閉包，這意味著可以訪問(wèn)在tco中定義的value，active以及accumulated

前面已經(jīng)講了，當(dāng)我們執(zhí)行sum的時(shí)候相當(dāng)于是執(zhí)行accumulator，于是accumulator 將實(shí)參傳入accumulated數(shù)組，比如執(zhí)行sum(1,10)那么這里傳入的就是類(lèi)數(shù)組對(duì)象[1，10]，accumulated現(xiàn)在就是一個(gè)length為1的二維數(shù)組。

進(jìn)入while循環(huán)，這里是關(guān)鍵：value = f.apply(this, accumulated.shift()); 在這條語(yǔ)句中， f表示外包的匿名函數(shù)，它判斷y的值后返回一個(gè)sum （這里很容易產(chǎn)生混亂，如果我們忽略while循環(huán)中的細(xì)節(jié)，很容易將其誤認(rèn)為也是遞歸）

匿名函數(shù)f判斷y的值返回一個(gè)sum，sum的參數(shù)被改變了，前面提到執(zhí)行sum相當(dāng)于執(zhí)行accumulator，于是新的參數(shù)被加入到了accumulator但是因?yàn)檫@時(shí)active的值依然是true（因?yàn)楝F(xiàn)在執(zhí)行流還在while循環(huán)里），所以執(zhí)行這個(gè)被返回的sum就會(huì)得到一個(gè)undefined的值，value被賦值為undefined

可是因?yàn)閳?zhí)行了被返回的sum（也就是執(zhí)行了accumulator）盡管沒(méi)有進(jìn)入if(!active),但是執(zhí)行了第一條語(yǔ)句，所以accumulated被重新push進(jìn)了在外包的匿名函數(shù)中被修改的實(shí)參，所以while循環(huán)繼續(xù)（理解這里是關(guān)鍵）。

while循環(huán)一直執(zhí)行到accumulated中的值為空， 在value = f.apply(this, accumulated.shift()); 每次return一次sum后accumulated 都會(huì)被重新推入一個(gè)實(shí)參（accumulated的length始終為1），直到匿名的外包函數(shù)return出x，于是x的值被賦給value被返回出來(lái)。

注意：以上主要還是根據(jù)我自己的理解來(lái)闡述邏輯， 確實(shí)比較繞，作者原文寫(xiě)得更加詳細(xì)

以上方法就是在不改動(dòng)源碼的情況下實(shí)現(xiàn)的TCO優(yōu)化， 作者在該文章的Update中介紹了另外的非TCO的優(yōu)化遞歸的方法，不過(guò)篇幅有限就不再貼出來(lái)了，就我自身感覺(jué)而言，如果對(duì)算法的邏輯實(shí)現(xiàn)不感興趣， 大可以直接用Babel將深遞歸轉(zhuǎn)換成優(yōu)化后的形式。另外這也有一篇介紹JS中遞歸與循環(huán)的的文章，其中也有TCO優(yōu)化的相關(guān)介紹：
?Recursion in Functional JavaScript

感覺(jué)以上代碼的實(shí)際意義可能并沒(méi)有那么大， 為了寫(xiě)這篇博客也是耗了我一天，囧rz，但也挺佩服這哥們：“我靠，這也能想得到！”