某些問題更適合用遞歸解決。例如，斐波那契數(shù)列這樣的序列具有遞歸定義。序列中的每個數(shù)字都是序列中前兩個數(shù)字的和。需要構(gòu)建或遍歷樹狀數(shù)據(jù)結(jié)構(gòu)的問題也可以用遞歸來解決。訓(xùn)練自己進(jìn)行遞歸思考將賦予你強(qiáng)大的技能來解決此類問題。

在本教程中，我將逐步講解幾個遞歸函數(shù)的工作原理，並向你展示一些系統(tǒng)地定義遞歸函數(shù)的技術(shù)。

內(nèi)容：

• 什麼是遞歸？
• 數(shù)字遞歸
• 列表遞歸
• 構(gòu)建列表
• 尾遞歸
• 總結(jié)

什麼是遞歸？

遞歸定義的函數(shù)是用其簡化版本自身定義的函數(shù)。這是一個簡化的示例：

 function doA(n) {
    // ...
    if (n > 0) {
        doA(n-1);
    }
}

為了從概念上理解遞歸的工作原理，我們將看一個與代碼無關(guān)的示例。假設(shè)你負(fù)責(zé)接聽公司裡的電話。由於這是一家繁忙的公司，你的電話有多條電話線，因此你可以同時處理多個電話。每條電話線在聽筒上都有一個按鈕，當(dāng)有來電時，按鈕會閃爍。今天，當(dāng)你上班並打開電話時，有四條線路同時閃爍。所以你開始接聽所有電話。

你拿起第一條線並告訴他們：“請稍候?！比会崮隳闷鸬诙l線並將他們也放在待機(jī)狀態(tài)。接下來，你拿起第三條線並將他們放在待機(jī)狀態(tài)，依此類推。最後，當(dāng)你完成每個電話後，你回到之前的來電者，完成該電話並掛斷。

此示例中的每個電話都類似於函數(shù)中的遞歸調(diào)用。當(dāng)你接到電話時，它會被放入調(diào)用堆棧（用代碼來說）。如果你不能立即完成一個電話，你就把它放在待機(jī)狀態(tài)。如果你的函數(shù)調(diào)用無法立即計算，它將保留在調(diào)用堆棧中。當(dāng)你能夠接聽電話時，它就會被接起。當(dāng)你的代碼能夠計算函數(shù)調(diào)用時，它就會從堆棧中彈出。請記住這個比喻，當(dāng)你查看以下代碼示例時。

數(shù)字遞歸

所有遞歸函數(shù)都需要一個基本情況，以便它們能夠終止。但是，僅僅向我們的函數(shù)添加一個基本情況並不能阻止它無限運(yùn)行。該函數(shù)必須有一個步驟來使我們更接近基本情況。這就是遞歸步驟。在遞歸步驟中，問題被簡化為問題的較小版本。

假設(shè)你有一個函數(shù)可以將從n 開始的所有數(shù)字相乘。這稱為階乘函數(shù)，我們將其寫為4!，如果n 等於1。

在每個步驟中，你將從當(dāng)前數(shù)字中減去1。遞歸情況是什麼？遞歸情況是函數(shù)fact(4)。

16. 4 等於1 嗎？否。放入fact(3)。
17. 3 等於1 嗎？否。放入fact(2)。
18. 2 等於1 嗎？否。放入fact(1)。
19. 1 等於1 嗎？是。返回fact(2) 並返回2。
20. 獲取3 * fact(2) 是fact(4) 並返回24。

這是另一種查看函數(shù)如何處理每個調(diào)用的方法：

 <code>fact(4) 4 * fact(3) 4 * ( 3 * fact(2) ) 4 * ( 3 * ( 2 * fact(1) )) 4 * ( 3 * ( 2 * 1 ) ) 4 * ( 3 * 2 ) 4 * 6 24</code>

在遞歸情況下，參數(shù)應(yīng)該改變並使你更接近基本情況。應(yīng)該在基本情況下測試此參數(shù)。在前面的示例中，因為我們在遞歸情況下減去1，所以在基本情況下我們測試參數(shù)是否等於0。

挑戰(zhàn)

1. 使用循環(huán)而不是遞歸實現(xiàn)sum 函數(shù)。
2. 創(chuàng)建一個遞歸地將兩個數(shù)字相乘的函數(shù)。例如，0；否則，你返回數(shù)組的第一個元素加上sum 調(diào)用。
3. 簡化filter 函數(shù)，使其從列表中刪除所有項目的出現(xiàn)。例如，["a", "b", "d"]。

尾遞歸

尾遞歸是一種遞歸形式，它允許編譯器執(zhí)行尾調(diào)用優(yōu)化(TCO) 以防止普通遞歸的許多性能缺陷。此外，尾遞歸解決了函數(shù)調(diào)用最大深度的難題。但是，你必須以某種方式編寫函數(shù)才能使其工作。

尾遞歸適用於在函數(shù)末尾調(diào)用遞歸函數(shù)的函數(shù)。例如，以下是sum() 函數(shù)的尾遞歸版本：sum() 的整個返回值就是整個返回值，因此運(yùn)行時可以安全地丟棄外部函數(shù)並只返回內(nèi)部函數(shù)的結(jié)果。但是，許多人會被這樣的事情絆倒：

 function notTailRecursive(n) {
    // ...
    return notTailRecursive(n) 1
}

你可能認(rèn)為這使用了尾遞歸，因為遞歸函數(shù)是在最後調(diào)用的。但是，它沒有。這是因為JavaScript 必須返回到外部函數(shù)才能加1。你可以重寫它的方法之一是將1傳遞到參數(shù)中，這樣內(nèi)部函數(shù)就可以進(jìn)行該計算。

並非所有瀏覽器目前都支持尾調(diào)用優(yōu)化，但它在ES 標(biāo)準(zhǔn)中，因此我們將來可能會看到更多對它的支持。此外，它通常是一種很好的實踐，因為它通常會隔離對函數(shù)參數(shù)的更改。

挑戰(zhàn)

將本文中一個示例遞歸函數(shù)重構(gòu)為尾遞歸函數(shù)。

總結(jié)

遞歸函數(shù)有三個部分。第一個是基本情況，它是終止條件。第二個是使我們更接近基本情況的步驟。第三個是遞歸步驟，其中函數(shù)使用簡化的輸入調(diào)用自身。

遞歸就像迭代。任何你可以遞歸定義的函數(shù)也可以使用循環(huán)來定義。使用遞歸時要考慮的其他事項包括遞歸嵌套列表和優(yōu)化遞歸調(diào)用。

你可以將遞歸函數(shù)重構(gòu)為尾遞歸函數(shù)，這可以提供性能優(yōu)勢。

一個繼續(xù)學(xué)習(xí)遞歸的好資源是《The Little Schemer》這本書。它使用問答格式教你如何進(jìn)行遞歸思考。

這篇文章已更新，其中包含Jacob Jackson 的貢獻(xiàn)。 Jacob 是一位網(wǎng)絡(luò)開發(fā)人員、技術(shù)作家、自由職業(yè)者和開源貢獻(xiàn)者。

以上是使用JavaScript了解遞歸的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！