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

要點

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

遞歸的用途

遞歸是一種通過讓函數(shù)重復(fù)調(diào)用自身直到得到結(jié)果來迭代操作的技術(shù)。大多數(shù)循環(huán)都可以用遞歸樣式重寫，在某些函數(shù)式編程語言中，這種循環(huán)方法是默認的。

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

當(dāng)需要在循環(huán)中使用不同的參數(shù)重復(fù)調(diào)用同一個函數(shù)時，最好使用遞歸。雖然它可以用于許多情況，但它最有效的是解決涉及迭代分支的問題，例如分形數(shù)學(xué)、排序或遍歷復(fù)雜或非線性的數(shù)據(jù)結(jié)構(gòu)的節(jié)點。

遞歸在函數(shù)式編程語言中受到青睞的一個原因是，它允許構(gòu)建不需要使用局部變量設(shè)置和維護狀態(tài)的代碼。遞歸函數(shù)也很容易測試，因為它們很容易以純凈的方式編寫，對于任何給定的輸入都有一個特定且一致的返回值，并且不會對外部變量狀態(tài)產(chǎn)生副作用。

循環(huán)

遞歸可以應(yīng)用的一個經(jīng)典函數(shù)示例是階乘。這是一個函數(shù)，它返回一個數(shù)字反復(fù)乘以每個前一個整數(shù)的結(jié)果，一直到1。

例如，3的階乘是：

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

6的階乘是：

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

你可以看到這些結(jié)果有多快就變大了。你還可以看到我們一遍又一遍地重復(fù)相同的行為。我們?nèi)∫粋€乘法運算的結(jié)果，再乘以第二個值減1。然后我們一次又一次地這樣做，直到達到1。

使用for循環(huán)，創(chuàng)建迭代執(zhí)行此操作直到返回正確結(jié)果的函數(shù)并不困難：

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

這有效，但從函數(shù)式編程的角度來看，它并不優(yōu)雅。為了支持for循環(huán)然后返回結(jié)果，我們必須使用幾個維護和跟蹤狀態(tài)的局部變量。如果我們可以丟棄for循環(huán)，并采用更函數(shù)式的JavaScript方法，豈不是更簡潔？

遞歸

我們知道JavaScript允許我們編寫將函數(shù)作為參數(shù)的函數(shù)。那么，如果我們想使用我們正在編寫的實際函數(shù)并在運行它的上下文中執(zhí)行它呢？

這甚至可能嗎？當(dāng)然可以！例如，考慮這樣一個簡單的while循環(huán)：

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的值已更改，但循環(huán)已完成其打印每個值的作業(yè)，因為我們緩慢地從其中提取了狀態(tài)。

相同循環(huán)的遞歸版本可能更像這樣：

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

你看到我們?nèi)绾卧赾ountdown函數(shù)的定義中直接調(diào)用countdown函數(shù)了嗎？JavaScript像老板一樣處理它，并且只做你希望它做的事情。每次執(zhí)行countdown時，JavaScript都會跟蹤它從何處被調(diào)用，然后回溯到該函數(shù)調(diào)用的堆棧，直到完成。我們的函數(shù)也避免了修改任何變量的狀態(tài)，但仍然利用傳入的值來控制遞歸。

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

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

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

尾調(diào)用優(yōu)化

當(dāng)代JavaScript實現(xiàn)的一個問題是，它們沒有標(biāo)準(zhǔn)的方法來防止遞歸函數(shù)無限地堆積自身，并消耗內(nèi)存直到超過引擎的容量。JavaScript遞歸函數(shù)需要每次都跟蹤它們從何處被調(diào)用，以便它們能夠在正確的位置繼續(xù)執(zhí)行。

在許多函數(shù)式編程語言（如Haskell和Scheme）中，這是使用稱為尾調(diào)用優(yōu)化的技術(shù)來管理的。使用尾調(diào)用優(yōu)化，遞歸函數(shù)中的每個連續(xù)循環(huán)將立即發(fā)生，而不是堆積在內(nèi)存中。

理論上，尾調(diào)用優(yōu)化是ECMAScript 6（當(dāng)前JavaScript的下一個版本）標(biāo)準(zhǔn)的一部分，但是大多數(shù)平臺尚未完全實現(xiàn)它。

彈跳函數(shù)

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

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

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

我們還沒到那一步

遞歸是一項強大的技術(shù)，值得了解。在許多情況下，遞歸是解決復(fù)雜問題的最直接方法。但是，在ECMAScript 6在我們需要的地方用尾調(diào)用優(yōu)化完全實現(xiàn)之前，我們需要非常小心地應(yīng)用遞歸的方式和位置。

關(guān)于函數(shù)式JavaScript中遞歸的常見問題解答 (FAQs)

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

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

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

在JavaScript中，遞歸的工作原理是函數(shù)調(diào)用自身直到達到基本情況。該函數(shù)被劃分為基本情況和遞歸情況?；厩闆r返回一個值而無需再次調(diào)用函數(shù)，而遞歸情況則使用不同的參數(shù)再次調(diào)用函數(shù)。該函數(shù)繼續(xù)調(diào)用自身，直到達到基本情況，此時它開始返回值。

什么是JavaScript中的尾遞歸？

尾遞歸是一種特殊的遞歸，其中遞歸調(diào)用是函數(shù)中的最后一個操作。這很重要，因為它允許JavaScript引擎優(yōu)化遞歸，使用一種稱為尾調(diào)用優(yōu)化的技術(shù)。這可以顯著減少函數(shù)使用的內(nèi)存量，使其能夠處理更大的輸入。

使用JavaScript中的遞歸的優(yōu)點和缺點是什么？

遞歸可以通過將復(fù)雜問題分解為更簡單的問題來使代碼更簡潔易懂。它對于遍歷樹狀數(shù)據(jù)結(jié)構(gòu)等任務(wù)特別有用。但是，遞歸也可能不如迭代解決方案高效，如果實現(xiàn)不正確，可能會導(dǎo)致堆棧溢出錯誤。

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

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

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

在函數(shù)式編程中，遞歸通常用作循環(huán)的替代品。由于函數(shù)式編程不鼓勵使用可變狀態(tài)，因此可以使用遞歸來執(zhí)行重復(fù)操作而無需更改任何狀態(tài)。

所有遞歸函數(shù)都可以轉(zhuǎn)換為迭代函數(shù)嗎？

是的，理論上，所有遞歸函數(shù)都可以轉(zhuǎn)換為迭代函數(shù)。但是，迭代版本可能更復(fù)雜且更難以理解，特別是對于涉及復(fù)雜樹或圖遍歷的函數(shù)。

什么是JavaScript中的互遞歸？

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

如何調(diào)試JavaScript中的遞歸函數(shù)？

由于重復(fù)的函數(shù)調(diào)用，調(diào)試遞歸函數(shù)可能具有挑戰(zhàn)性。但是，使用console.log語句在每個步驟打印函數(shù)的參數(shù)和返回值可能會有所幫助。此外，使用允許您逐步執(zhí)行函數(shù)調(diào)用的調(diào)試器工具非常有用。

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

是的，由于重復(fù)函數(shù)調(diào)用的開銷，遞歸函數(shù)可能不如其迭代對應(yīng)物高效。如果它們調(diào)用自身太多次，它們也可能導(dǎo)致堆棧溢出錯誤。但是，在許多情況下，遞歸解決方案的可讀性和簡單性可以超過這些性能方面的考慮。

以上是功能JavaScript中的遞歸的詳細內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！