功能JavaScript中的遞歸

JavaScript中的遞歸函數或許你已經聽說過，甚至嘗試編寫過一些。但你可能沒見過很多實際有效的遞歸示例。事實上，除了這種方法的特殊性之外，你可能還沒有考慮過遞歸何時何地有用，或者如果使用不當會多麼危險。

要點

• 遞歸是一種JavaScript方法，允許函數重複調用自身，直到達到結果。它對於涉及迭代分支的問題特別有用，例如分形數學、排序或遍歷複雜或非線性的數據結構。
• 雖然遞歸可以使代碼更簡潔易懂，但如果使用不當，由於存在超過引擎內存容量的風險，它可能是危險的。這是因為JavaScript遞歸函數需要每次都跟踪它們從何處被調用，以便它們能夠在正確的位置繼續執行。
• 在許多函數式編程語言中，一種稱為尾調用優化的技術用於管理遞歸。這允許遞歸函數中的每個連續循環立即發生，而不是堆積在內存中。但是，大多數JavaScript編譯器目前尚未針對此進行優化。
• 可以構建自定義彈跳函數來迭代地管理遞歸執行，一次只在堆棧上保留一個操作。這可以幫助避免創建等待執行的深度堆棧操作，但通常是以犧牲性能和可讀性為代價的。

遞歸的用途

遞歸是一種通過讓函數重複調用自身直到得到結果來迭代操作的技術。大多數循環都可以用遞歸樣式重寫，在某些函數式編程語言中，這種循環方法是默認的。

但是，雖然JavaScript的函數式編程風格支持遞歸函數，但我們需要意識到大多數JavaScript編譯器目前還沒有針對它們進行安全優化。

當需要在循環中使用不同的參數重複調用同一個函數時，最好使用遞歸。雖然它可以用於許多情況，但它最有效的是解決涉及迭代分支的問題，例如分形數學、排序或遍歷複雜或非線性的數據結構的節點。

遞歸在函數式編程語言中受到青睞的一個原因是，它允許構建不需要使用局部變量設置和維護狀態的代碼。遞歸函數也很容易測試，因為它們很容易以純淨的方式編寫，對於任何給定的輸入都有一個特定且一致的返回值，並且不會對外部變量狀態產生副作用。

循環

遞歸可以應用的一個經典函數示例是階乘。這是一個函數，它返回一個數字反复乘以每個前一個整數的結果，一直到1。

例如，3的階乘是：

<code>3 × 2 × 1 = 6</code>

6的階乘是：

<code>3 × 2 × 1 = 6</code>

你可以看到這些結果有多快就變大了。你還可以看到我們一遍又一遍地重複相同的行為。我們取一個乘法運算的結果，再乘以第二個值減1。然後我們一次又一次地這樣做，直到達到1。

使用for循環，創建迭代執行此操作直到返回正確結果的函數並不困難：

<code>6 × 5 × 4 × 3 × 2 × 1 = 720</code>

這有效，但從函數式編程的角度來看，它並不優雅。為了支持for循環然後返回結果，我們必須使用幾個維護和跟踪狀態的局部變量。如果我們可以丟棄for循環，並採用更函數式的JavaScript方法，豈不是更簡潔？

遞歸

我們知道JavaScript允許我們編寫將函數作為參數的函數。那麼，如果我們想使用我們正在編寫的實際函數並在運行它的上下文中執行它呢？

這甚至可能嗎？當然可以！例如，考慮這樣一個簡單的while循環：

var factor = function(number) {
  var result = 1;
  var count;
  for (count = number; count > 1; count--) {
    result *= count;
  }
  return result;
};
console.log(factor(6));
// 720

完成此操作後，counter的值已更改，但循環已完成其打印每個值的作業，因為我們緩慢地從其中提取了狀態。

相同循環的遞歸版本可能更像這樣：

var counter = 10;
while(counter > 0) {
    console.log(counter--);
}

你看到我們如何在countdown函數的定義中直接調用countdown函數了嗎？ JavaScript像老闆一樣處理它，並且只做你希望它做的事情。每次執行countdown時，JavaScript都會跟踪它從何處被調用，然後回溯到該函數調用的堆棧，直到完成。我們的函數也避免了修改任何變量的狀態，但仍然利用傳入的值來控制遞歸。

回到我們的階乘案例，我們可以這樣重寫之前的函數以使用遞歸：

var countdown = function(value) {
    if (value > 0) {
        console.log(value);
        return countdown(value - 1);
    } else {
        return value;
    }
};
countdown(10);

以這種方式編寫代碼允許我們以無狀態的方式描述整個過程，沒有任何副作用。同樣值得注意的是，我們首先測試傳遞給函數的參數的值，然後再進行任何計算。我們希望任何將要調用自身的函數在到達其終止情況時都能快速乾淨地退出。對於以這種方式計算的階乘，當傳入的數字為零或負數時，會到達終止情況（如果我們希望，我們也可以測試負值並返回不同的消息）。

尾調用優化

當代JavaScript實現的一個問題是，它們沒有標準的方法來防止遞歸函數無限地堆積自身，並消耗內存直到超過引擎的容量。 JavaScript遞歸函數需要每次都跟踪它們從何處被調用，以便它們能夠在正確的位置繼續執行。

在許多函數式編程語言（如Haskell和Scheme）中，這是使用稱為尾調用優化的技術來管理的。使用尾調用優化，遞歸函數中的每個連續循環將立即發生，而不是堆積在內存中。

理論上，尾調用優化是ECMAScript 6（當前JavaScript的下一個版本）標準的一部分，但是大多數平台尚未完全實現它。

彈跳函數

如有必要，有一些方法可以強制JavaScript以安全的方式執行遞歸函數。例如，可以構建自定義彈跳函數來迭代地管理遞歸執行，一次只在堆棧上保留一個操作。以這種方式使用的彈跳函數可以利用JavaScript將函數綁定到特定上下文的能力，以便將遞歸函數彈回自身，一次構建一個結果，直到循環完成。這將避免創建等待執行的深度堆棧操作。

實際上，使用彈跳函數通常會為了安全而降低性能。此外，我們通過以遞歸方式編寫函數獲得的大部分優雅性和可讀性都會在使這種方法在JavaScript中起作用所需的代碼卷積中丟失。

如果你好奇，我鼓勵你閱讀更多關於這個概念的信息，並在下面的討論中分享你的想法。你可以從StackOverflow上的一個簡短主題開始，然後探索Don Taylor和Mark McDonnell的一些文章，這些文章更深入地探討了JavaScript中彈跳函數的優缺點。

我們還沒到那一步

遞歸是一項強大的技術，值得了解。在許多情況下，遞歸是解決複雜問題的最直接方法。但是，在ECMAScript 6在我們需要的地方用尾調用優化完全實現之前，我們需要非常小心地應用遞歸的方式和位置。

關於函數式JavaScript中遞歸的常見問題解答 (FAQs)

遞歸中的基本情況是什麼？為什麼它很重要？

遞歸中的基本情況是阻止函數無限調用自身的條件。它至關重要，因為如果沒有它，遞歸函數將無限地調用自身，導致堆棧溢出錯誤。基本情況通常是函數在進行遞歸調用之前檢查的條件。如果滿足該條件，則函數返回一個值並停止調用自身。

遞歸在JavaScript中是如何工作的？

在JavaScript中，遞歸的工作原理是函數調用自身直到達到基本情況。該函數被劃分為基本情況和遞歸情況。基本情況返回一個值而無需再次調用函數，而遞歸情況則使用不同的參數再次調用函數。該函數繼續調用自身，直到達到基本情況，此時它開始返回值。

什麼是JavaScript中的尾遞歸？

尾遞歸是一種特殊的遞歸，其中遞歸調用是函數中的最後一個操作。這很重要，因為它允許JavaScript引擎優化遞歸，使用一種稱為尾調用優化的技術。這可以顯著減少函數使用的內存量，使其能夠處理更大的輸入。

使用JavaScript中的遞歸的優點和缺點是什麼？

遞歸可以通過將復雜問題分解為更簡單的問題來使代碼更簡潔易懂。它對於遍歷樹狀數據結構等任務特別有用。但是，遞歸也可能不如迭代解決方案高效，如果實現不正確，可能會導致堆棧溢出錯誤。

如何避免遞歸函數中的堆棧溢出錯誤？

當遞歸函數調用自身太多次，填滿調用堆棧時，就會發生堆棧溢出錯誤。為避免這種情況，請確保您的遞歸函數具有最終將達到的基本情況。此外，請考慮使用尾遞歸，JavaScript引擎可以對其進行優化以使用更少的內存。

遞歸在函數式編程中是如何使用的？

在函數式編程中，遞歸通常用作循環的替代品。由於函數式編程不鼓勵使用可變狀態，因此可以使用遞歸來執行重複操作而無需更改任何狀態。

所有遞歸函數都可以轉換為迭代函數嗎？

是的，理論上，所有遞歸函數都可以轉換為迭代函數。但是，迭代版本可能更複雜且更難以理解，特別是對於涉及復雜樹或圖遍歷的函數。

什麼是JavaScript中的互遞歸？

互遞歸是指兩個或多個函數以循環方式相互調用。這可能是解決某些類型問題的強大技術，但它也可能比簡單的遞歸更難理解和調試。

如何調試JavaScript中的遞歸函數？

由於重複的函數調用，調試遞歸函數可能具有挑戰性。但是，使用console.log語句在每個步驟打印函數的參數和返回值可能會有所幫助。此外，使用允許您逐步執行函數調用的調試器工具非常有用。

使用遞歸時是否存在任何性能方面的考慮？

是的，由於重複函數調用的開銷，遞歸函數可能不如其迭代對應物高效。如果它們調用自身太多次，它們也可能導致堆棧溢出錯誤。但是，在許多情況下，遞歸解決方案的可讀性和簡單性可以超過這些性能方面的考慮。

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