? ? 1遞歸需要滿(mǎn)足的三個(gè)條件

? ? ? ? 1.一個(gè)問(wèn)題的解可以分解為幾個(gè)子問(wèn)題的解。

? ? ? ? 2.這個(gè)問(wèn)題與分解之后的子問(wèn)題局服，除了數(shù)據(jù)規(guī)模不同钓瞭，求解思路完全一樣。

? ? ? ? 3.存在遞歸終止條件腌逢。

????2如何編寫(xiě)遞歸代碼降淮？

????????寫(xiě)遞歸代碼最關(guān)鍵的是寫(xiě)出遞歸公式，找到終止條件，然后再將遞推公式轉(zhuǎn)化為代碼佳鳖。

? ? ? ? 用一個(gè)例子來(lái)理解~

? ? ? ? 假設(shè)有n個(gè)臺(tái)階霍殴，每次可以跨1個(gè)臺(tái)階或者2個(gè)臺(tái)階，那么這n個(gè)臺(tái)階有多少種走法系吩？

? ? ? ? 實(shí)際上来庭，可以根據(jù)第一步的走法把所有走法分為兩類(lèi)，第一類(lèi)是第一步走了1個(gè)臺(tái)階穿挨， 第二類(lèi)是第一步走了2個(gè)臺(tái)階月弛。所以，n個(gè)臺(tái)階的走法=先走1階后剩下n-1個(gè)臺(tái)階的走法+先走2階后剩下n-2個(gè)臺(tái)階的走法科盛，公式如下：

? ? ? ? f(n)=f(n-1)+f(n-2)? ?

? ? ? ? 終止條件為：f(1)=1,f(2)=2.

? ? ? ? 轉(zhuǎn)化成代碼：

? ? ? ? 寫(xiě)遞歸代碼的關(guān)鍵就是找到如何將大問(wèn)題分解為小問(wèn)題的規(guī)律帽衙，并且基于此寫(xiě)出遞推公式，然后再推敲終止條件贞绵，最后將遞推公式和終止條件翻譯成代碼厉萝。

? ? ? ? 遞歸分為兩個(gè)過(guò)程，去的過(guò)程叫“遞”榨崩，回來(lái)的過(guò)程叫“歸”谴垫。

? ? ? ? 計(jì)算機(jī)擅長(zhǎng)做重復(fù)的事情，所以遞歸正和它的胃口母蛛。

? ? 3遞歸代碼要警惕堆棧溢出

? ? ? ? 之前學(xué)習(xí)“楐婕簦”的時(shí)候，我們知道函數(shù)調(diào)用會(huì)使用棧來(lái)保存臨時(shí)變量彩郊，每調(diào)用一個(gè)函數(shù)前弯，都會(huì)將臨時(shí)變量封裝為棧幀壓入內(nèi)存棧，等函數(shù)執(zhí)行完成返回時(shí)秫逝，才出棧博杖。系統(tǒng)棧或者虛擬機(jī)椏甑牵空間一般都不大，而如果遞歸求解的數(shù)據(jù)規(guī)模很大哩盲、調(diào)用層次很深的話(huà)前方，一直壓入棧就會(huì)有堆棧溢出的風(fēng)險(xiǎn)。

? ? ? ? 如何避免出現(xiàn)堆棧溢出呢廉油？

? ? ? ? 可以通過(guò)在代碼中限制遞歸調(diào)用的最大深度的方式來(lái)解決這個(gè)問(wèn)題惠险。遞歸調(diào)用超過(guò)一定深度（比如1000）之后，我們就不繼續(xù)往下再遞歸了抒线，直接返回報(bào)錯(cuò)班巩。

? ? ? ? 一個(gè)偽代碼的例子：

? ? ? ? 但這種做法并不能完全解決問(wèn)題，因?yàn)樽畲笤试S的遞歸深度跟當(dāng)前線(xiàn)程剩余的棧空間大小有關(guān)抱慌，事先無(wú)法計(jì)算逊桦。如果實(shí)時(shí)計(jì)算，代碼過(guò)于復(fù)雜抑进，會(huì)影響代碼的可讀性强经。所以如果最大深度比較小，就可以用這種方法寺渗，否則這種方法并不是很實(shí)用匿情。

? ? 4遞歸代碼要警惕重復(fù)計(jì)算

? ? ? ? 使用遞歸的時(shí)候還會(huì)出現(xiàn)重復(fù)計(jì)算的問(wèn)題，比如我們剛才講的例子：

? ? ? ? 可以看到信殊，同一個(gè)f(k)我們會(huì)計(jì)算好幾次炬称。為了避免重復(fù)計(jì)算，我們可以通過(guò)一個(gè)數(shù)據(jù)結(jié)構(gòu)（比如散列表）來(lái)保存已經(jīng)求解過(guò)的f(k)涡拘。每次遞歸調(diào)用到f(k)的時(shí)候玲躯，先看下是否已經(jīng)求解過(guò)了，如果是鲸伴，則直接從散列表中取值返回府蔗。

? ? ? ? OK，優(yōu)化后的代碼如下：

? ? 5怎么將遞歸代碼改寫(xiě)為非遞歸代碼汞窗？

? ? ? ? 遞歸有利有弊姓赤，利是遞歸代碼的表達(dá)能力強(qiáng)，寫(xiě)起來(lái)非常簡(jiǎn)潔仲吏；弊是空間復(fù)雜度高不铆、有堆棧溢出的風(fēng)險(xiǎn)、存在重復(fù)計(jì)算裹唆、過(guò)多的函數(shù)調(diào)用會(huì)耗時(shí)較多等問(wèn)題誓斥。所以在開(kāi)發(fā)過(guò)程中，我們要根據(jù)實(shí)際情況來(lái)選擇是否需要通過(guò)遞歸的方式來(lái)實(shí)現(xiàn)许帐。

? ? ? ? 那如何將遞歸代碼改寫(xiě)為非遞歸代碼呢劳坑？

? ? ? ? 例一：

? ? ? ? 遞歸代碼：

? ? ? ? 非遞歸代碼：

? ? ? ? 例二（上臺(tái)階的例子）：

? ? ? ? 遞歸代碼：

? ? ? ? 非遞歸代碼：

? ? ? ? 所有的遞歸代碼都可以改為這種迭代循環(huán)的非遞歸寫(xiě)法嗎？

? ? ? ? 是的成畦。

? ? ? ? 因?yàn)檫f歸本身就是借助棧來(lái)實(shí)現(xiàn)的距芬，只不過(guò)我們使用的棧是系統(tǒng)或者虛擬機(jī)本身提供的，我們沒(méi)有感知罷了循帐。如果我們自己在內(nèi)存堆上實(shí)現(xiàn)棧框仔，手動(dòng)模擬入棧、出棧過(guò)程拄养，這樣任何遞歸代碼都可以改寫(xiě)成看上去不是遞歸代碼的樣子离斩。

? ? ? ? 但是這種思路實(shí)際上是將遞歸改為了“手動(dòng)”遞歸，本質(zhì)并沒(méi)有變，而且也并沒(méi)有解決前面講到的某些問(wèn)題跛梗，徒增了實(shí)現(xiàn)的復(fù)雜度寻馏。

????內(nèi)容小結(jié)

? ? ? ? 遞歸是一種非常高效、簡(jiǎn)潔的編碼技巧茄袖，只要滿(mǎn)足“三個(gè)條件”的問(wèn)題就可以通過(guò)遞歸代碼來(lái)解決操软。不過(guò)遞歸代碼也比較難寫(xiě)、難理解宪祥。編寫(xiě)遞歸代碼的正確姿勢(shì)是寫(xiě)出遞推公式聂薪，找出終止條件，然后翻譯成遞歸代碼蝗羊。遞歸代碼雖然簡(jiǎn)潔高效藏澳，但是也有很多弊端，比如堆棧溢出耀找、重復(fù)計(jì)算翔悠、函數(shù)調(diào)用耗時(shí)多、空間復(fù)雜度高等野芒，所以在編寫(xiě)遞歸代碼的時(shí)候蓄愁，一定要控制好這些副作用。