摘要：一旦我們滿足了基本條件值為，我們將不再調用遞歸函數，只是有效地執行了。遞歸深諳函數式編程之精髓，最被廣泛引證的原因是，在調用棧中，遞歸把大部分顯式狀態跟蹤換為了隱式狀態。

原文地址：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

在下一頁，我們將進入到遞歸的論題。

(本頁剩余部分故意留白)

?

?

?

?

?

?

?

?

?

?

?

我們來談談遞歸吧。在我們入坑之前，請查閱上一頁的正式定義。

我知道，這個笑話弱爆了 :)

大部分的開發人員都承認遞歸是一門非常強大的編程技術，但他們并不喜歡去使用它。在這個意義上，我把它放在與正則表達式相同的類別中。遞歸技術強大但又令人困惑，因此被視為 不值得我們投入努力。

我是遞歸編程的超級粉絲，你，也可以的！在這一章節中我的目標就是說服你：遞歸是一個重要的工具，你應該將它用在你的函數式編程中。當你正確使用時，遞歸編程可以輕松地描述復雜問題。

所謂遞歸，是當一個函數調用自身，并且該調用做了同樣的事情，這個循環持續到基本條件滿足時，調用循環返回。

警告： 如果你不能確保基本條件是遞歸的 終結者，遞歸將會一直執行下去，并且會把你的項目損壞或鎖死；恰當的基本條件十分重要！

但是... 這個定義的書面形式太讓人疑惑了。我們可以做的更好些。思考下這個遞歸函數：

function foo(x) {
    if (x < 5) return x;
    return foo( x / 2 );
}

設想一下，如果我們調用 foo(16) 將會發生什么：

在 step 2 中, x / 2 的結果是 8， 這個結果以參數的形式傳遞到 foo(..) 并運行。同樣的，在 step 3 中， x / 2 的結果是 4，這個結果以參數的形式傳遞到另一個 foo(..) 并運行。但愿我解釋得足夠直白。

但是一些人經常會在 step 4 中卡殼。一旦我們滿足了基本條件 x (值為4) < 5，我們將不再調用遞歸函數，只是（有效地）執行了 return 4。
特別是圖中返回 4 的虛線那塊，它簡化了那里的過程，因此我們來深入了解最后一步，并把它折分為三個子步驟：

該次的返回值會回過頭來觸發調用棧中所有的函數調用（并且它們都執行 return）。

另外一個遞歸實例：

function isPrime(num,divisor = 2){
    if (num < 2 || (num > 2 && num % divisor == 0)) {
        return false;
    }
    if (divisor <= Math.sqrt( num )) {
        return isPrime( num, divisor + 1 );
    }

    return true;
}

這個質數的判斷主要是通過驗證，從2到 num 的平方根之間的每個整數，看是否存在某一整數可以整除 num (% 求余結果為 0)。如果存在這樣的整數，那么 num 不是質數。反之，是質數。divisor + 1 使用遞歸來遍歷每個可能的 divisor 值。

遞歸的最著名的例子之一是計算斐波那契數，該數列定義如下：

fib( 0 ): 0
fib( 1 ): 1
fib( n ):
    fib( n - 2 ) + fib( n - 1 )

注意: 數列的前幾個數值是： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 每一個數字都是數列中前兩個數字之和。

直接用代碼來定義斐波那契：

function fib(n) {
    if (n <= 1) return n;
    return fib( n - 2 ) + fib( n - 1 );
}

函數 fib(..) 對自身進行了兩次遞歸調用，這通常叫作二分遞歸查找。后面我們將會更多地討論二分遞歸查找。

在整個章節中，我們將會用不同形式的 fib(..) 來說明關于遞歸的想法，但不太好的地方就是，這種特殊的方式會造成很多重復性的工作。 fib(n-1) 和?fib(n-2) 運行時候兩者之間并沒有任何的共享，但做的事情幾乎又完全相同，這種情況一直持續到整個整數空間(譯者注：形參 n)降到 0 。

在第五章的性能優化方面我們簡單的談到了記憶存儲技術。本章中，記憶存儲技術使得任意一個傳入到 fib(..) 的數值只會被計算一次而不是多次。雖然我們不會在這里過多地討論這個技術話題，但不論是遞歸或其它任何算法，我們都要謹記，性能優化是非常重要的。

當一個函數調用自身時，很明顯，這叫作直接遞歸。比如前面部分我們談到的 foo(..)，isPrime(..)以及 fib(..)。如果在一個遞歸循環中，出現兩個及以上的函數相互調用，則稱之為相互遞歸。

這兩個函數就是相互遞歸：

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 );
}

是的，這個奇偶數的判斷笨笨的。但也給我們提供了一些思路：某些算法可以根據相互遞歸來定義。

回顧下上節中的二分遞歸法 fib(..)；我們可以換成相互遞歸來表示：

function fib_(n) {
    if (n == 1) return 1;
    else return fib( n - 2 );
}

function fib(n) {
    if (n == 0) return 0;
    else return fib( n - 1 ) + fib_( n );
}

注意： fib(..) 相互遞歸的實現方式改編自 “用相互遞歸來實現斐波納契數列” 研究報告(https://www.researchgate.net/... 。

雖然這些相互遞歸的示例有點不切實際，但是在更復雜的使用場景下，相互遞歸是非常有用的。

現在我們已經給出了遞歸的定義和說明，下面來看下，為什么說遞歸是有用的。

遞歸深諳函數式編程之精髓，最被廣泛引證的原因是，在調用棧中，遞歸把(大部分)顯式狀態跟蹤換為了隱式狀態。通常，當問題需要條件分支和回溯計算時，遞歸非常有用，此外在純迭代環境中管理這種狀態，是相當棘手的；最起碼，這些代碼是不可或缺且晦澀難懂。但是在堆棧上調用每一級的分支作為其自己的作用域，很明顯，這通常會影響到代碼的可讀性。

簡單的迭代算法可以用遞歸來表達：

function sum(total,...nums) {
    for (let i = 0; i < nums.length; i++) {
        total = total + nums[i];
    }

    return total;
}

// vs

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

我們不僅用調用棧代替了 for 循環，而且用 returns 的形式在回調棧中隱式地跟蹤增量的求和（ total 的間歇狀態），而非在每次迭代中重新分配 total。通常，FPer 傾向于盡可能地避免重新分配局部變量。

像我們總結的那樣，在基本算法里，這些差異是微乎其微的。但是，隨著算法復雜度的提升，你將更加能體會到遞歸帶來的收益，而不是這些命令式狀態跟蹤。

數學家使用 Σ 符號來表示一列數字的總和。主要原因是，如果他們使用更復雜的公式而且不得不手動書寫求和的話，會造成更多麻煩（而且會降低閱讀性！），比如
1 + 3 + 5 + 7 + 9 + ..。符號是數學的聲明式語言！

正如 Σ 是為運算而聲明，遞歸是為算法而聲明。遞歸說明：一個問題存在解決方案，但并不一定要求閱讀代碼的人了解該解決方案的工作原理。我們來思考下找出入參最大偶數值的兩種方法：

function maxEven(...nums) {
    var num = -Infinity;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] % 2 == 0 && nums[i] > num) {
            num = nums[i];
        }
    }

    if (num !== -Infinity) {
        return num;
    }
}

這種實現方式不是特別難處理，但它的一些細微的問題也不容忽視。很明顯，運行 maxEven()，maxEven(1) 和 maxEven(1,13) 都將會返回 undefined？最終的 if 語句是必需的嗎？

我們試著換一個遞歸的方法來對比下。我們用下面的符號來表示遞歸：

maxEven( nums ):
    maxEven( nums.0, maxEven( ...nums.1 ) )

換句話說，我們可以將數字列表的 max-even 定義為其余數字的 max-even 與第一個數字的 max-even 的結果。例如：

maxEven( 1, 10, 3, 2 ):
    maxEven( 1, maxEven( 10, maxEven( 3, maxEven( 2 ) ) )

在 JS 中實現這個遞歸定義的方法之一是：

function maxEven(num1,...restNums) {
    var maxRest = restNums.length > 0 ?
            maxEven( ...restNums ) :
            undefined;

    return (num1 % 2 != 0 || num1 < maxRest) ?
        maxRest :
        num1;
}

那么這個方法有什么優點嗎？

首先，參數與之前不一樣了。我專門把第一個參數叫作 num1，剩余的其它參數放在一起叫作 restNums。我們本可以把所有參數都放在 nums 數組中，并從 nums[0] 獲取第一個參數。這是為什么呢？

函數的參數是專門為遞歸定義的。它看起來像這樣：

maxEven( num1, ...restNums ):
    maxEven( num1, maxEven( ...restNums ) )

你有發現參數和遞歸之間的相似性嗎？

當我們在函數體簽名中進一步提升遞歸的定義，函數的聲明也會得到提升。如果我們能夠把遞歸的定義從參數反映到函數體中，那就更棒了。

但我想說最明顯的改進是，for 循環造成的錯亂感沒有了。所有循環邏輯都被抽象為遞歸回調棧，所以這些東西不會造成代碼混亂。我們可以輕松的把精力集中在一次比較兩個數字來找到最大偶數值的邏輯中 —— 不管怎么說，這都是很重要的部分！

從思想上來講，這如同一位數學家在更龐大的方程中使用 Σ 求和一樣。我們說，“數列中剩余值的最大偶數是通過 maxEven(...restNums) 計算出來的，所以我們只需要繼續推斷這一部分。”

另外，我們用 restNums.length > 0 保證推斷更加合理，因為當沒有參數的情況下，返回的 maxRest 結果肯定是 undefined。我們不需要對這部分的推理投入額外的精力。這個基本條件（沒有參數情況下）顯而易見。

接下來，我們把精力放在對比 num1 和 maxRest 上 —— 算法的主要邏輯是如何確定兩個數字中的哪一個（如果有的話）是最大偶數。如果 num1 不是偶數（num1 % 2 != 0），或著它小于 maxRest，那么，即使 maxRest 的值是 undefined，maxRest 會 return 掉。否則，返回結果會是 num1。

在閱讀整個實現過程中，與命令式的方法相比，我所做這個例子的推理過程更加直接，核心點更加突出，少做無用功；比 for 循環中引用 無窮數值 這一方法 更具有聲明性。

小貼士： 我們應該指出，除了手動迭代或遞歸之外，另一種（可能更好的）建模的方法是我們在在第7章中討論的列表操作。我們先把數列中的偶數用 filter(..) 過濾出來，然后通過遞歸 reduce(..) 函數（對比兩個數值并返回其中較大的數值）來找到最大值。在這里，我們只是使用這個例子來說明在手動迭代中遞歸的聲明性更強。

還有一個遞歸的例子：計算二叉樹的深度。二叉樹的深度是指通過樹的節點向下（左或右）的最長路徑。還有另一種通過遞歸來定義的方式：任何樹節點的深度為1（當前節點）加上來自其左側或右側子樹的深度的最大值：

depth( node ):
    1 + max( depth( node.left ), depth( node.right ) )

直接轉換為二分法遞歸函數：

function depth(node) {
    if (node) {
        let depthLeft = depth( node.left );
        let depthRight = depth( node.right );
        return 1 + max( depthLeft, depthRight );
    }

    return 0;
}

我不打算列出這個算法的命令式形式，但請相信我，它太麻煩、過于命令式了。這種遞歸方法很不錯，聲明也很優雅。它遵循遞歸的定義，與遞歸定義的算法非常接近，省心。

并不是所有的問題都是完全可遞歸的。它不是你可以廣泛應用的靈丹妙藥。但是遞歸可以非常有效地將問題的表達，從更具必要性轉變為更有聲明性。

未完待續......【下一章】第 9 章：遞歸(下)

【上一章】翻譯連載 | JavaScript輕量級函數式編程-第 8 章：列表操作 |《你不知道的JS》姊妹篇

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