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

要點(diǎn)

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

遞歸的用途

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

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

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

遞歸在函數(shù)式編程語(yǔ)言中受到青睞的一個(gè)原因是，它允許構(gòu)建不需要使用局部變量設(shè)置和維護(hù)狀態(tài)的代碼。遞歸函數(shù)也很容易測(cè)試，因?yàn)樗鼈兒苋菀滓约儍舻姆绞骄帉懀瑢?duì)于任何給定的輸入都有一個(gè)特定且一致的返回值，并且不會(huì)對(duì)外部變量狀態(tài)產(chǎn)生副作用。

循環(huán)

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

例如，3的階乘是：

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

6的階乘是：

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

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

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

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

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

遞歸

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

這甚至可能嗎？當(dāng)然可以！例如，考慮這樣一個(gè)簡(jiǎn)單的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)已完成其打印每個(gè)值的作業(yè)，因?yàn)槲覀兙徛貜钠渲刑崛×藸顟B(tài)。

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

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

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

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

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

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

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

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

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

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

彈跳函數(shù)

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

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

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

我們還沒(méi)到那一步

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

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

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

遞歸中的基本情況是阻止函數(shù)無(wú)限調(diào)用自身的條件。它至關(guān)重要，因?yàn)槿绻麤](méi)有它，遞歸函數(shù)將無(wú)限地調(diào)用自身，導(dǎo)致堆棧溢出錯(cuò)誤?；厩闆r通常是函數(shù)在進(jìn)行遞歸調(diào)用之前檢查的條件。如果滿足該條件，則函數(shù)返回一個(gè)值并停止調(diào)用自身。

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

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

什么是JavaScript中的尾遞歸？

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

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

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

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

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

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

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

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

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

什么是JavaScript中的互遞歸？

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

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

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

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

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

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