摘要：每個函數調用都將開辟出一小塊稱為堆棧幀的內存。當第二個函數開始執行，堆棧幀增加到個。當這個函數調用結束后，它的幀會從堆棧中退出。保持堆棧幀跟蹤函數調用的狀態，并將其分派給下一個遞歸調用迭。

原文地址：Functional-Light-JS

原文作者：Kyle Simpson－《You-Dont-Know-JS》作者

關于譯者：這是一個流淌著滬江血液的純粹工程：認真，是 HTML 最堅實的梁柱；分享，是 CSS  里最閃耀的一瞥；總結，是 JavaScript 中最嚴謹的邏輯。經過捶打磨練，成就了本書的中文版。本書包含了函數式編程之精髓，希望可以幫助大家在學習函數式編程的道路上走的更順暢。比心。
譯者團隊（排名不分先后）：阿希、blueken、brucecham、cfanlife、dail、kyoko-df、l3ve、lilins、LittlePineapple、MatildaJin、冬青、pobusama、Cherry、蘿卜、vavd317、vivaxy、萌萌、zhouyao

一起看下之前的兩個遞歸函數 isOdd(..) 和 isEven(..)：

function isOdd(v) {
    if (v === 0) return false;
    return isEven( Math.abs( v ) - 1 );
}

function isEven(v) {
    if (v === 0) return true;
    return isOdd( Math.abs( v ) - 1 );
}

如果你執行下面這行代碼，在大多數瀏覽器里面都會報錯：

isOdd( 33333 );            // RangeError: Maximum call stack size exceeded

這個錯誤是什么情況？引擎拋出這個錯誤，是因為它試圖保護系統內存不會被你的程序耗盡。為了解釋這個問題，我們需要先看看當函數調用時JS引擎中發生了什么。

每個函數調用都將開辟出一小塊稱為堆棧幀的內存。堆棧幀中包含了函數語句當前狀態的某些重要信息，包括任意變量的值。之所以這樣，是因為一個函數暫停去執行另外一個函數，而另外一個函數運行結束后，引擎需要返回到之前暫停時候的狀態繼續執行。

當第二個函數開始執行，堆棧幀增加到 2 個。如果第二個函數又調用了另外一個函數，堆棧幀將增加到 3 個，以此類推。“棧”的意思是，函數被它前一個函數調用時，這個函數幀會被“推”到最頂部。當這個函數調用結束后，它的幀會從堆棧中退出。

看下這段程序：

function foo() {
    var z = "foo!";
}

function bar() {
    var y = "bar!";
    foo();
}

function baz() {
    var x = "baz!";
    bar();
}

baz();

來一步步想象下這個程序的堆棧幀：

注意： 如果這些函數間沒有相互調用，而只是依次執行 -- 比如前一個函數運行結束后才開始調用下一個函數 baz(); bar(); foo(); -- 則堆棧幀并沒有產生；因為在下一個函數開始之前，上一個函數運行結束并把它的幀從堆棧里面移除了。

所以，每一個函數運行時候，都會占用一些內存。對多數程序來說，這沒什么大不了的，不是嗎？但是，一旦你引用了遞歸，問題就不一樣了。
雖然你幾乎肯定不會在一個調用棧中手動調用成千（或數百）次不同的函數，但你很容易看到產生數萬個或更多遞歸調用的堆棧。

當引擎認為調用棧增加的太多并且應該停止增加時候，它會以主觀的限制來阻止當前步驟，所以 isOdd(..) 或 isEven(..) 函數拋出了 RangeError 未知錯誤。這不太可能是內存接近零時候產生的限制，而是引擎的預測，因為如果這種程序持續運行下去，內存會爆掉的。由于引擎無法判斷一個程序最終是否會停止，所以它必須做出確定的猜測。

引擎的限制因情況而定。規范里面并沒有任何說明，因此，它也不是 必需的。但如果沒有限制的話，設備很容易遭到破壞或惡意代碼攻擊，故而幾乎所有的JS引擎都有一個限制。不同的設備環境、不同的引擎，會有不同的限制，也就無法預測或保證函數調用棧能調用多少次。

在處理大數據量時候，這個限制對于開發人員來說，會對遞歸的性能有一定的要求。我認為，這種限制也可能是造成開發人員不喜歡使用遞歸編程的最大原因。
遺憾的是，遞歸編程是一種編程思想而不是主流的編程技術。

遞歸編程和內存限制都要比 JS 技術出現的早。追溯到上世紀 60 年代，當時開發人員想使用遞歸編程并希望運行在他們強大的計算機的設備，而所謂強大計算機的內存，尚遠不如我們今天在手表上的內存。

幸運的是，在那個希望的原野上，進行了一個有力的觀測。該技術稱為 尾調用。

它的思路是如果一個回調從函數 baz() 轉到函數 bar() 時候，而回調是在函數 baz() 的最底部執行 -- 也就是尾調用 -- 那么 baz() 的堆棧幀就不再需要了。也就意謂著，內存可以被回收，或只需簡單的執行 bar() 函數。 如圖所示：

尾調用并不是遞歸特有的；它適用于任何函數調用。但是，在大多數情況下，你的手動非遞歸調用棧不太可能超過 10 級，因此尾調用對你程序內存的影響可能相當低。

在遞歸的情況下，尾調用作用很明顯，因為這意味著遞歸堆棧可以“永遠”運行下去，唯一的性能問題就是計算，而不再是固定的內存限制。在固定的內存中尾遞歸可以運行 O(1) （常數階時間復雜度計算）。

這些技術通常被稱為尾調用優化（TCO），但重點在于從優化技術中，區分出在固定內存空間中檢測尾調用運行的能力。從技術上講，尾調用并不像大多數人所想的那樣，它們的運行速度可能比普通回調還慢。TCO 是關于把尾調用更加高效運行的一些優化技術。

在 ES6 出來之前，JavaScript 對尾調用一直沒明確規定（也沒有禁用）。ES6 明確規定了 PTC 的特定形式，在 ES6 中，只要使用尾調用，就不會發生棧溢出。實際上這也就意味著，只要正確的使用 PTC，就不會拋出 RangeError 這樣的異常錯誤。

首先，在 JavaScript 中應用 PTC，必須以嚴格模式書寫代碼。如果你以前沒有用過嚴格模式，你得試著用用了。那么，您，應該已經在使用嚴格模式了吧！？

其次，正確 的尾調用就像這個樣子：

return foo( .. );

換句話說，函數調用應該放在最后一步去執行，并且不管返回什么東東，都得有返回（ return ）。這樣的話，JS 就不再需要當前的堆棧幀了。

下面這些 不能 稱之為 PTC：

foo();
return;

// 或

var x = foo( .. );
return x;

// 或

return 1 + foo( .. );

注意： 一些 JS 引擎 能夠 把 var x = foo(); return x; 自動識別為 return foo();，這樣也可以達到 PTC 的效果。但這畢竟不符合規范。

foo(..) 運行結束之后 1+ 這部分才開始執行，所以此時的堆棧幀依然存在。

不過，下面這個 是 PTC：

return x ? foo( .. ) : bar( .. );

x 進行條件判斷之后，或執行 foo(..)，或執行 bar(..)，不論執行哪個，返回結果都會被 return 返回掉。這個例子符合 PTC 規范。

為了避免堆棧增加，PTC 要求所有的遞歸必須是在尾部調用，因此，二分法遞歸 —— 兩次（或以上）遞歸調用 —— 是不能實現 PTC 的。我們曾在文章的前面部分展示過把二分法遞歸轉變為相互遞歸的例子。也許我們可以試著化整為零，把多重遞歸拆分成符合 PTC 規范的單個函數回調。

如果你想用遞歸來處理問題，卻又超出了 JS 引擎的內存堆棧，這時候就需要重構下你的遞歸調用，使它能夠符合 PTC 規范（或著避免嵌套調用）。這里有一些重構方法也許可以用到，但需要根據實際情況權衡。

可讀性強的代碼，是我們的終級目標 —— 謹記，謹記。如果使用遞歸后會造成代碼難以閱讀/理解，那就 不要使用遞歸；換個容易理解的方法吧。

對遞歸來說，最主要的問題是它的內存使用情況。保持堆棧幀跟蹤函數調用的狀態，并將其分派給下一個遞歸調用迭。如果我們弄清楚了如何重新排列我們的遞歸，就可以用 PTC 實現遞歸，并利用 JS 引擎對尾調用的優化處理，那么我們就不用在內存中保留當前的堆棧幀了。

來回顧下之前用到的一個求和的例子：

function sum(num1,...nums) {
    if (nums.length == 0) return num1;
    return num1 + sum( ...nums );
}

這個例子并不符合 PTC 規范。sum(...nums) 運行結束之后，num1 與 sum(...nums) 的運行結果進行了累加。這樣的話，當其余參數 ...nums 再次進行遞歸調用時候，為了得到其與 num1 累加的結果，必須要保留上一次遞歸調用的堆棧幀。

重構策略的關鍵點在于，我們可以通過把 置后 處理累加改為 提前 處理，來消除對堆棧的依賴，然后將該部分結果作為參數傳遞到遞歸調用。換句話說，我們不用在當前運用函數的堆棧幀中保留 num1 + sum(...num1) 的總和，而是把它傳遞到下一個遞歸的堆棧幀中，這樣就能釋放當前遞歸的堆棧幀。

開始之前，我們做些改動：把部分結果作為一個新的第一個參數傳入到函數 sum(..)：

function sum(result,num1,...nums) {
    // ..
}

這次我們先把 result 和 num1 提前計算，然后把 result 作為參數一起傳入：

"use strict";

function sum(result,num1,...nums) {
    result = result + num1;
    if (nums.length == 0) return result;
    return sum( result, ...nums );
}

現在 sum(..) 已經符合 PTC 優化規范了！耶！

但是還有一個缺點，我們修改了函數的參數傳遞形式后，用法就跟以前不一樣了。調用者不得不在需要求和的那些參數的前面，再傳遞一個 0 作為第一個參數。

sum( /*initialResult=*/0, 3, 1, 17, 94, 8 );        // 123

這就尷尬了。

通常，大家的處理方式是，把這個尷尬的遞歸函數重新命名，然后定義一個接口函數把問題隱藏起來：

"use strict";

function sumRec(result,num1,...nums) {
    result = result + num1;
    if (nums.length == 0) return result;
    return sumRec( result, ...nums );
}

function sum(...nums) {
    return sumRec( /*initialResult=*/0, ...nums );
}

sum( 3, 1, 17, 94, 8 );                                // 123

情況好了些。但依然有問題：之前只需要一個函數就能解決的事，現在我們用了兩個。有時候你會發現，在處理這類問題上，有些開發者用內部函數把遞歸 “藏了起來”：

"use strict";

function sum(...nums) {
    return sumRec( /*initialResult=*/0, ...nums );

    function sumRec(result,num1,...nums) {
        result = result + num1;
        if (nums.length == 0) return result;
        return sumRec( result, ...nums );
    }
}

sum( 3, 1, 17, 94, 8 );                                // 123

這個方法的缺點是，每次調用外部函數 sum(..)，我們都得重新創建內部函數 sumRec(..)。我們可以把他們平級放置在立即執行的函數中，只暴露出我們想要的那個的函數：

"use strict";

var sum = (function IIFE(){

    return function sum(...nums) {
        return sumRec( /*initialResult=*/0, ...nums );
    }

    function sumRec(result,num1,...nums) {
        result = result + num1;
        if (nums.length == 0) return result;
        return sumRec( result, ...nums );
    }

})();

sum( 3, 1, 17, 94, 8 );                                // 123

好啦，現在即符合了 PTC 規范，又保證了 sum(..) 參數的整潔性，調用者不需要了解函數的內部實現細節。完美！

可是...天吶，本來是簡單的遞歸函數，現在卻出現了很多噪點。可讀性已經明顯降低。至少說，這是不成功的。有些時候，這只是我們能做的最好的。

幸運的事，在一些其它的例子中，比如上一個例子，有一個比較好的方式。一起重新看下：

"use strict";

function sum(result,num1,...nums) {
    result = result + num1;
    if (nums.length == 0) return result;
    return sum( result, ...nums );
}

sum( /*initialResult=*/0, 3, 1, 17, 94, 8 );        // 123

也許你會注意到，result 就像 num1 一樣，也就是說，我們可以把列表中的第一個數字作為我們的運行總和；這甚至包括了第一次調用的情況。我們需要的是重新命名這些參數，使函數清晰可讀：

"use strict";

function sum(num1,num2,...nums) {
    num1 = num1 + num2;
    if (nums.length == 0) return num1;
    return sum( num1, ...nums );
}

sum( 3, 1, 17, 94, 8 );                                // 123

帥呆了。比之前好了很多，嗯？！我認為這種模式在聲明/合理和執行之間達到了很好的平衡。

讓我們試著重構下前面的 maxEven(..)（目前還不符合 PTC 規范）。就像之前我們把參數的和作為第一個參數一樣，我們可以依次減少列表中的數字，同時一直把遇到的最大偶數作為第一個參數。

為了清楚起見，我們可能使用算法策略（類似于我們之前討論過的）：

首先對前兩個參數 num1 和 num2 進行對比。

如果 num1 是偶數，并且 num1 大于 num2，num1 保持不變。

如果 num2 是偶數，把 num2 賦值給 num1。

否則的話，num1 等于 undefined。

如果除了這兩個參數之外，還存在其它參數 nums，把它們與 num1 進行遞歸對比。

最后，不管是什么值，只需返回 num1。

依照上面的步驟，代碼如下：

"use strict";

function maxEven(num1,num2,...nums) {
    num1 =
        (num1 % 2 == 0 && !(maxEven( num2 ) > num1)) ?
            num1 :
            (num2 % 2 == 0 ? num2 : undefined);

    return nums.length == 0 ?
        num1 :
        maxEven( num1, ...nums )
}

注意： 函數第一次調用 maxEven(..) 并不是為了 PTC 優化，當它只傳遞 num2 時，只遞歸一級就返回了；它只是一個避免重復 ％ 邏輯的技巧。因此，只要該調用是完全不同的函數，就不會增加遞歸堆棧。第二次調用 maxEven(..) 是基于 PTC 優化角度的真正遞歸調用，因此不會隨著遞歸的進行而造成堆棧的增加。

重申下，此示例僅用于說明將遞歸轉化為符合 PTC 規范以優化堆棧（內存）使用的方法。求最大偶數值的更直接方法可能是，先對參數列表中的 nums 過濾，然后冒泡或排序處理。

基于 PTC 重構遞歸，固然對簡單的聲明形式有一些影響，但依然有理由去做這樣的事。不幸的是，存在一些遞歸，即使我們使用了接口函數來擴展，也不會很好，因此，我們需要有不同的思路。

在 JavaScript 中， continuation 一詞通常用于表示在某個函數完成后指定需要執行的下一個步驟的回調函數。組織代碼，使得每個函數在其結束時接收另一個執行函數，被稱為后繼傳遞格式（CPS）。

有些形式的遞歸，實際上是無法按照純粹的 PTC 規范重構的，特別是相互遞歸。我們之前提到過的 fib(..) 函數，以及我們派生出來的相互遞歸形式。這兩個情況，皆是存在多個遞歸調用，這些遞歸調用阻礙了 PTC 內存優化。

但是，你可以執行第一個遞歸調用，并將后續遞歸調用包含在后續函數中并傳遞到第一個調用。盡管這意味著最終需要在堆棧中執行更多的函數，但由于后繼函數所包含的都是 PTC 形式的，所以堆棧內存的使用情況不會無限增長。

把 fib(..) 做如下修改：

"use strict";

function fib(n,cont = identity) {
    if (n <= 1) return cont( n );
    return fib(
        n - 2,
        n2 => fib(
            n - 1,
            n1 => cont( n2 + n1 )
        )
    );
}

仔細看下都做了哪些事情。首先，我們默認用了第三章中的 cont(..) 后繼函數表示 identity(..)；記住，它只簡單的返回傳遞給它的任何東西。

更重要的是，這里面增加了不僅僅是一個而是兩個后續函數。第一個后續函數接收 fib(n-2) 的運行結果作為參數 n2。第二個內部后續函數接收 fib(n-1)的運行結果作為參數 n1。當得到 n1 和 n2 的值后，兩者再相加 （n2 + n1），相加的運行結果會傳入到下一個后續函數 cont(..)。

也許這將有助于我們梳理下流程：就像我們之前討論的，在遞歸堆棧之后，當我們傳遞部分結果而不是返回它們時，每一步都被包含在一個后續函數中，這拖慢了計算速度。這個技巧允許我們執行多個符合 PTC 規范的步驟。

在靜態語言中，CPS通常為尾調用提供了編譯器可以自動識別并重新排列遞歸代碼以利用的機會。很可惜，不能用在原生 JS 上。

在 JavaScript 中，你得自己書寫出符合 CPS 格式的代碼。這并不是明智的做法；以命令符號聲明的形式肯定會讓內容有些不清楚。 但總的來說，這種形式仍然要比 for 循環更具有聲明性。

警告： 我們需要注意的一個比較重要的事項是，在 CPS 中，創建額外的內部后續函數仍然消耗內存，但有些不同。并不是之前的堆棧幀累積，閉包只是消耗多余的內存空間（一般情況下，是堆棧里面的多余內存空間）。在這些情況下，引擎似乎沒有啟動 RangeError 限制，但這并不意味著你的內存使用量是按比例固定好的。

除了 CPS 后續傳遞格式之外，另外一種內存優化的技術稱為彈簧床。在彈簧床格式的代碼中，同樣的創建了類似 CPS 的后續函數，不同的是，它們沒有被傳遞，而是被簡單的返回了。

不再是函數調用另外的函數，堆棧的深度也不會大于一層，因為每個函數只會返回下一個將調用的函數。循環只是繼續運行每個返回的函數，直到再也沒有函數可運行。

彈簧床的優點之一是在非 PTC 環境下你一樣可以應用此技術。另一個優點是每個函數都是正常調用，而不是 PTC 優化，所以它可以運行得更快。

一起來試下 trampoline(..)：

function trampoline(fn) {
    return function trampolined(...args) {
        var result = fn( ...args );

        while (typeof result == "function") {
            result = result();
        }

        return result;
    };
}

當返回一個函數時，循環繼續，執行該函數并返回其運行結果，然后檢查返回結果的類型。一旦返回的結果類型不是函數，彈簧床就認為函數調用完成了并返回結果值。

所以我們可能需要使用前面講到的，將部分結果作為參數傳遞的技巧。以下是我們在之前的數組求和中使用此技巧的示例：

var sum = trampoline(
    function sum(num1,num2,...nums) {
        num1 = num1 + num2;
        if (nums.length == 0) return num1;
        return () => sum( num1, ...nums );
    }
);

var xs = [];
for (let i=0; i<20000; i++) {
    xs.push( i );
}

sum( ...xs );                    // 199990000

缺點是你需要將遞歸函數包裹在執行彈簧床功能的函數中; 此外，就像 CPS 一樣，需要為每個后續函數創建閉包。然而，與 CPS 不一樣的地方是，每個返回的后續數數，運行并立即完成，所以，當調用堆棧的深度用盡時，引擎中不會累積越來越多的閉包。

除了執行和記憶性能之外，彈簧床技術優于CPS的優點是它們在聲明遞歸形式上的侵入性更小，由于你不必為了接收后續函數的參數而更改函數參數，所以除了執行和內存性能之外，彈簧床技術優于 CPS 的地方還有，它們在聲明遞歸形式上侵入性更小。雖然彈簧床技術并不是理想的，但它們可以有效地在命令循環代碼和聲明性遞歸之間達到平衡。

遞歸，是指函數遞歸調用自身。呃，這就是遞歸的定義。明白了吧！？

直遞歸是指對自身至少調用一次，直到滿足基本條件才能停止調用。多重遞歸（像二分遞歸）是指對自身進行多次調用。相互遞歸是當兩個或以上函數循環遞歸 相互 調用。而遞歸的優點是它更具聲明性，因此通常更易于閱讀。

遞歸的優點是它更具聲明性，因此通常更易于閱讀。缺點通常是性能方面，但是相比執行速度，更多的限制在于內存方面。

尾調用是通過減少或釋放堆棧幀來節約內存空間。要在 JavaScript 中實現尾調用 “優化”，需要基于嚴格模式和適當的尾調用（ PTC ）。我們也可以混合幾種技術來將非 PTC 遞歸函數重構為 PTC 格式，或者至少能通過平鋪堆棧來節約內存空間。

謹記：遞歸應該使代碼更容易讀懂。如果你誤用或濫用遞歸，代碼的可讀性將會比命令形式更糟。千萬不要這樣做。

【上一章】翻譯連載 | 第 9 章：遞歸（上）－《JavaScript輕量級函數式編程》 |《你不知道的JS》姊妹篇

iKcamp原創新書《移動Web前端高效開發實戰》已在亞馬遜、京東、當當開售。
滬江Web前端上海團隊招聘【Web前端架構師】，有意者簡歷至：zhouyao@hujiang.com