使用JavaScript了解遞歸

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

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

內容：

• 什麼是遞歸？
• 數字遞歸
• 列表遞歸
• 構建列表
• 尾遞歸
• 總結

什麼是遞歸？

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

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

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

你拿起第一條線並告訴他們：“請稍候。”然後你拿起第二條線並將他們也放在待機狀態。接下來，你拿起第三條線並將他們放在待機狀態，依此類推。最後，當你完成每個電話後，你回到之前的來電者，完成該電話並掛斷。

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

數字遞歸

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

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

在每個步驟中，你將從當前數字中減去1。遞歸情況是什麼？遞歸情況是函數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。

這是另一種查看函數如何處理每個調用的方法：

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

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

挑戰

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

尾遞歸

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

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

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

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

並非所有瀏覽器目前都支持尾調用優化，但它在ES 標準中，因此我們將來可能會看到更多對它的支持。此外，它通常是一種很好的實踐，因為它通常會隔離對函數參數的更改。

挑戰

將本文中一個示例遞歸函數重構為尾遞歸函數。

總結

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

遞歸就像迭代。任何你可以遞歸定義的函數也可以使用循環來定義。使用遞歸時要考慮的其他事項包括遞歸嵌套列表和優化遞歸調用。

你可以將遞歸函數重構為尾遞歸函數，這可以提供性能優勢。

一個繼續學習遞歸的好資源是《The Little Schemer》這本書。它使用問答格式教你如何進行遞歸思考。

這篇文章已更新，其中包含Jacob Jackson 的貢獻。 Jacob 是一位網絡開發人員、技術作家、自由職業者和開源貢獻者。

以上是使用JavaScript了解遞歸的詳細內容。更多資訊請關注PHP中文網其他相關文章！