面試官：遞歸是個(gè)什么東東？

今天的主題本來(lái)是兩個(gè)：

遞歸
堆棧但是由于篇幅太長(zhǎng)，我們分為兩部分進(jìn)行，今天先來(lái)講講遞歸，我們平常可能會(huì)用到遞歸，簡(jiǎn)單來(lái)說(shuō)就是自己調(diào)用自己，例如，我們的遞歸組件，遞歸函數(shù)求和，等等。但是我們從來(lái)沒(méi)有仔細(xì)研究下這遞歸到底有什么優(yōu)缺點(diǎn)？

本文你應(yīng)該帶著兩個(gè)問(wèn)題進(jìn)行閱讀

什么是遞歸
如何使用遞歸

什么是遞歸

遞歸是一種編程模式，在一種任務(wù)可以自然地拆分為相同類(lèi)型的多個(gè)任務(wù)，但更簡(jiǎn)單的情況下很有用。或者，當(dāng)一個(gè)任務(wù)可以簡(jiǎn)化為一個(gè)簡(jiǎn)單的動(dòng)作以及該任務(wù)的一個(gè)更簡(jiǎn)單的變體時(shí)。或者，正如我們將很快看到的那樣，處理某些數(shù)據(jù)結(jié)構(gòu)。

當(dāng)一個(gè)函數(shù)解決任務(wù)時(shí)，在此過(guò)程中它可以調(diào)用許多其他函數(shù)。這種情況的部分情況是函數(shù)調(diào)用自身時(shí)。這就是所謂的遞歸。

兩種思維方式

舉個(gè)簡(jiǎn)單的例子，比如我們求 x 的 n 次冪，這個(gè)時(shí)候我們可能需要用到遞歸：

pow(2,?2)?=?4
pow(2,?3)?=?8
pow(2,?4)?=?16

第一種，迭代思維

最經(jīng)常使用就是使用 for 循環(huán)：

function?pow(x,?n)?{
??let?result?=?1;

??//?multiply?result?by?x?n?times?in?the?loop
??for?(let?i?=?0;?i?????result?*=?x;
??}

??return?result;
}

alert(?pow(2,?3)?);?//?8

第二種，遞歸思維

function?pow(x,?n)?{
??if?(n?==?1)?{
????return?x;
??}?else?{
????return?x?*?pow(x,?n?-?1);
??}
}

alert(?pow(2,?3)?);?//?8

值得注意的是，遞歸變體在本質(zhì)上是不同的。

當(dāng)pow(x, n)被調(diào)用時(shí)，執(zhí)行分成兩個(gè)分支：

??????????????if?n==1??=?x
?????????????/
pow(x,?n)?=
?????????????\
??????????????else?????=?x?*?pow(x,?n?-?1)

如果為n == 1，那么一切都是微不足道的。之所以稱(chēng)為遞歸基礎(chǔ)，是因?yàn)樗⒓串a(chǎn)生明顯的結(jié)果：pow(x, 1)equals x。
否則，我們可以表示pow(x, n)為x * pow(x, n - 1)。在數(shù)學(xué)中，人們會(huì)寫(xiě)。這稱(chēng)為遞歸步驟：我們將任務(wù)轉(zhuǎn)換為更簡(jiǎn)單的動(dòng)作（乘以）和對(duì)同一任務(wù)的更簡(jiǎn)單調(diào)用（使用）。接下來(lái)的步驟進(jìn)一步和進(jìn)一步簡(jiǎn)化，直到達(dá)到 n == 1。

我們也可以說(shuō)pow 遞歸調(diào)用自己直到n == 1。

例如，要計(jì)算pow(2, 4)遞歸變量，請(qǐng)執(zhí)行以下步驟：

pow(2,?4)?=?2?*?pow(2,?3)
pow(2,?3)?=?2?*?pow(2,?2)
pow(2,?2)?=?2?*?pow(2,?1)
pow(2,?1)?=?2

因此，遞歸將函數(shù)調(diào)用簡(jiǎn)化為一個(gè)更簡(jiǎn)單的函數(shù)調(diào)用，然后再簡(jiǎn)化為一個(gè)更簡(jiǎn)單的函數(shù)，依此類(lèi)推，直到結(jié)果變得明顯為止。

遞歸通常較短

遞歸解通常比迭代解短。

function?pow(x,?n)?{
??return?(n?==?1)???x?:?(x?*?pow(x,?n?-?1));
}

嵌套調(diào)用（包括第一個(gè)）的最大數(shù)量稱(chēng)為遞歸深度。在我們的情況下，它將是n

最大遞歸深度受JavaScript引擎限制。我們可以依靠它為10000，某些引擎允許更多，但是對(duì)于大多數(shù)引擎來(lái)說(shuō)100000可能已超出限制。有一些自動(dòng)優(yōu)化可以幫助緩解這種情況（“尾部?jī)?yōu)化”），但是尚無(wú)處支持它們，并且僅在簡(jiǎn)單情況下有效。

那限制了遞歸的應(yīng)用，但是它仍然非常廣泛。在許多任務(wù)中，遞歸思維方式使代碼更簡(jiǎn)單，更易于維護(hù)。

明天我們繼續(xù)往下講。