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

原文地址：Functional-Light-JS

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

關(guān)于譯者：這是一個(gè)流淌著滬江血液的純粹工程：認(rèn)真，是 HTML 最堅(jiān)實(shí)的梁柱；分享，是 CSS  里最閃耀的一瞥；總結(jié)，是 JavaScript 中最嚴(yán)謹(jǐn)?shù)倪壿嫛＝?jīng)過(guò)捶打磨練，成就了本書(shū)的中文版。本書(shū)包含了函數(shù)式編程之精髓，希望可以幫助大家在學(xué)習(xí)函數(shù)式編程的道路上走的更順暢。比心。
譯者團(tuán)隊(duì)（排名不分先后）：阿希、blueken、brucecham、cfanlife、dail、kyoko-df、l3ve、lilins、LittlePineapple、MatildaJin、冬青、pobusama、Cherry、蘿卜、vavd317、vivaxy、萌萌、zhouyao

在下一頁(yè)，我們將進(jìn)入到遞歸的論題。

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

?

?

?

?

?

?

?

?

?

?

?

我們來(lái)談?wù)勥f歸吧。在我們?nèi)肟又埃?qǐng)查閱上一頁(yè)的正式定義。

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

大部分的開(kāi)發(fā)人員都承認(rèn)遞歸是一門(mén)非常強(qiáng)大的編程技術(shù)，但他們并不喜歡去使用它。在這個(gè)意義上，我把它放在與正則表達(dá)式相同的類別中。遞歸技術(shù)強(qiáng)大但又令人困惑，因此被視為 不值得我們投入努力。

我是遞歸編程的超級(jí)粉絲，你，也可以的！在這一章節(jié)中我的目標(biāo)就是說(shuō)服你：遞歸是一個(gè)重要的工具，你應(yīng)該將它用在你的函數(shù)式編程中。當(dāng)你正確使用時(shí)，遞歸編程可以輕松地描述復(fù)雜問(wèn)題。

所謂遞歸，是當(dāng)一個(gè)函數(shù)調(diào)用自身，并且該調(diào)用做了同樣的事情，這個(gè)循環(huán)持續(xù)到基本條件滿足時(shí)，調(diào)用循環(huán)返回。

警告： 如果你不能確?；緱l件是遞歸的 終結(jié)者，遞歸將會(huì)一直執(zhí)行下去，并且會(huì)把你的項(xiàng)目損壞或鎖死；恰當(dāng)?shù)幕緱l件十分重要！

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

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

設(shè)想一下，如果我們調(diào)用 foo(16) 將會(huì)發(fā)生什么：

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

但是一些人經(jīng)常會(huì)在 step 4 中卡殼。一旦我們滿足了基本條件 x (值為4) < 5，我們將不再調(diào)用遞歸函數(shù)，只是（有效地）執(zhí)行了 return 4。
特別是圖中返回 4 的虛線那塊，它簡(jiǎn)化了那里的過(guò)程，因此我們來(lái)深入了解最后一步，并把它折分為三個(gè)子步驟：

該次的返回值會(huì)回過(guò)頭來(lái)觸發(fā)調(diào)用棧中所有的函數(shù)調(diào)用（并且它們都執(zhí)行 return）。

另外一個(gè)遞歸實(shí)例：

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

這個(gè)質(zhì)數(shù)的判斷主要是通過(guò)驗(yàn)證，從2到 num 的平方根之間的每個(gè)整數(shù)，看是否存在某一整數(shù)可以整除 num (% 求余結(jié)果為 0)。如果存在這樣的整數(shù)，那么 num 不是質(zhì)數(shù)。反之，是質(zhì)數(shù)。divisor + 1 使用遞歸來(lái)遍歷每個(gè)可能的 divisor 值。

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

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

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

直接用代碼來(lái)定義斐波那契：

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

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

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

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

當(dāng)一個(gè)函數(shù)調(diào)用自身時(shí)，很明顯，這叫作直接遞歸。比如前面部分我們談到的 foo(..)，isPrime(..)以及 fib(..)。如果在一個(gè)遞歸循環(huán)中，出現(xiàn)兩個(gè)及以上的函數(shù)相互調(diào)用，則稱之為相互遞歸。

這兩個(gè)函數(shù)就是相互遞歸：

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

是的，這個(gè)奇偶數(shù)的判斷笨笨的。但也給我們提供了一些思路：某些算法可以根據(jù)相互遞歸來(lái)定義。

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

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(..) 相互遞歸的實(shí)現(xiàn)方式改編自 “用相互遞歸來(lái)實(shí)現(xiàn)斐波納契數(shù)列” 研究報(bào)告(https://www.researchgate.net/... 。

雖然這些相互遞歸的示例有點(diǎn)不切實(shí)際，但是在更復(fù)雜的使用場(chǎng)景下，相互遞歸是非常有用的。

現(xiàn)在我們已經(jīng)給出了遞歸的定義和說(shuō)明，下面來(lái)看下，為什么說(shuō)遞歸是有用的。

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

簡(jiǎn)單的迭代算法可以用遞歸來(lái)表達(dá)：

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

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

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

數(shù)學(xué)家使用 Σ 符號(hào)來(lái)表示一列數(shù)字的總和。主要原因是，如果他們使用更復(fù)雜的公式而且不得不手動(dòng)書(shū)寫(xiě)求和的話，會(huì)造成更多麻煩（而且會(huì)降低閱讀性！），比如
1 + 3 + 5 + 7 + 9 + ..。符號(hào)是數(shù)學(xué)的聲明式語(yǔ)言！

正如 Σ 是為運(yùn)算而聲明，遞歸是為算法而聲明。遞歸說(shuō)明：一個(gè)問(wèn)題存在解決方案，但并不一定要求閱讀代碼的人了解該解決方案的工作原理。我們來(lái)思考下找出入?yún)⒆畲笈紨?shù)值的兩種方法：

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

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

我們?cè)囍鴵Q一個(gè)遞歸的方法來(lái)對(duì)比下。我們用下面的符號(hào)來(lái)表示遞歸：

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

換句話說(shuō)，我們可以將數(shù)字列表的 max-even 定義為其余數(shù)字的 max-even 與第一個(gè)數(shù)字的 max-even 的結(jié)果。例如：

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

在 JS 中實(shí)現(xiàn)這個(gè)遞歸定義的方法之一是：

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

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

那么這個(gè)方法有什么優(yōu)點(diǎn)嗎？

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

函數(shù)的參數(shù)是專門(mén)為遞歸定義的。它看起來(lái)像這樣：

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

你有發(fā)現(xiàn)參數(shù)和遞歸之間的相似性嗎？

當(dāng)我們?cè)诤瘮?shù)體簽名中進(jìn)一步提升遞歸的定義，函數(shù)的聲明也會(huì)得到提升。如果我們能夠把遞歸的定義從參數(shù)反映到函數(shù)體中，那就更棒了。

但我想說(shuō)最明顯的改進(jìn)是，for 循環(huán)造成的錯(cuò)亂感沒(méi)有了。所有循環(huán)邏輯都被抽象為遞歸回調(diào)棧，所以這些東西不會(huì)造成代碼混亂。我們可以輕松的把精力集中在一次比較兩個(gè)數(shù)字來(lái)找到最大偶數(shù)值的邏輯中 —— 不管怎么說(shuō)，這都是很重要的部分！

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

另外，我們用 restNums.length > 0 保證推斷更加合理，因?yàn)楫?dāng)沒(méi)有參數(shù)的情況下，返回的 maxRest 結(jié)果肯定是 undefined。我們不需要對(duì)這部分的推理投入額外的精力。這個(gè)基本條件（沒(méi)有參數(shù)情況下）顯而易見(jiàn)。

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

在閱讀整個(gè)實(shí)現(xiàn)過(guò)程中，與命令式的方法相比，我所做這個(gè)例子的推理過(guò)程更加直接，核心點(diǎn)更加突出，少做無(wú)用功；比 for 循環(huán)中引用 無(wú)窮數(shù)值 這一方法 更具有聲明性。

小貼士： 我們應(yīng)該指出，除了手動(dòng)迭代或遞歸之外，另一種（可能更好的）建模的方法是我們?cè)谠诘?章中討論的列表操作。我們先把數(shù)列中的偶數(shù)用 filter(..) 過(guò)濾出來(lái)，然后通過(guò)遞歸 reduce(..) 函數(shù)（對(duì)比兩個(gè)數(shù)值并返回其中較大的數(shù)值）來(lái)找到最大值。在這里，我們只是使用這個(gè)例子來(lái)說(shuō)明在手動(dòng)迭代中遞歸的聲明性更強(qiáng)。

還有一個(gè)遞歸的例子：計(jì)算二叉樹(shù)的深度。二叉樹(shù)的深度是指通過(guò)樹(shù)的節(jié)點(diǎn)向下（左或右）的最長(zhǎng)路徑。還有另一種通過(guò)遞歸來(lái)定義的方式：任何樹(shù)節(jié)點(diǎn)的深度為1（當(dāng)前節(jié)點(diǎn)）加上來(lái)自其左側(cè)或右側(cè)子樹(shù)的深度的最大值：

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

直接轉(zhuǎn)換為二分法遞歸函數(shù)：

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

    return 0;
}

我不打算列出這個(gè)算法的命令式形式，但請(qǐng)相信我，它太麻煩、過(guò)于命令式了。這種遞歸方法很不錯(cuò)，聲明也很優(yōu)雅。它遵循遞歸的定義，與遞歸定義的算法非常接近，省心。

并不是所有的問(wèn)題都是完全可遞歸的。它不是你可以廣泛應(yīng)用的靈丹妙藥。但是遞歸可以非常有效地將問(wèn)題的表達(dá)，從更具必要性轉(zhuǎn)變?yōu)楦新暶餍浴?/p>

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

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

iKcamp原創(chuàng)新書(shū)《移動(dòng)Web前端高效開(kāi)發(fā)實(shí)戰(zhàn)》已在亞馬遜、京東、當(dāng)當(dāng)開(kāi)售。
滬江Web前端上海團(tuán)隊(duì)招聘【W(wǎng)eb前端架構(gòu)師】，有意者簡(jiǎn)歷至：zhouyao@hujiang.com