簡(jiǎn)介
使用遞歸可以更自然地解決一些問(wèn)題材泄。例如西疤，像斐波那契數(shù)列：數(shù)列中的每個(gè)數(shù)字都是數(shù)列中前兩個(gè)數(shù)字的和币绩。凡是需要您構(gòu)建或遍歷樹(shù)狀數(shù)據(jù)結(jié)構(gòu)的問(wèn)題基本都可以通過(guò)遞歸來(lái)解決，鍛煉自己強(qiáng)大的遞歸思維瘸羡，你會(huì)發(fā)現(xiàn)解決這類問(wèn)題十分容易漩仙。
在本文中，我將列舉兩個(gè)案例犹赖，讓你們了解遞歸函數(shù)是如何工作的队他。
綱要
- 什么是遞歸
- 數(shù)字的遞歸
- 數(shù)組的遞歸
- 總結(jié)
什么是遞歸
函數(shù)的遞歸就是在函數(shù)中調(diào)用自身，看一個(gè)簡(jiǎn)單的例子：
function doA(n) {
...
doA(n-1);
}
為了理解遞歸在理論上是如何工作的峻村，我們先舉一個(gè)與代碼無(wú)關(guān)的例子麸折。想象一下，你是一家公司的話務(wù)員雀哨。由于這是一家業(yè)務(wù)繁忙的公司磕谅，你的座機(jī)連接多條線路私爷，因此你可以同時(shí)處理多個(gè)電話雾棺。每條線路對(duì)應(yīng)接收器上的一個(gè)按鈕，當(dāng)有來(lái)電時(shí)衬浑，該按鈕將閃爍捌浩。今天當(dāng)你到達(dá)公司開(kāi)始工作時(shí)，發(fā)現(xiàn)有四條線路對(duì)應(yīng)的按鈕正在閃爍工秩，所以你需要接聽(tīng)所有這些電話尸饺。
你接通線路一，并告訴他“請(qǐng)稍等”助币，然后你接通線路二浪听，并告訴他“請(qǐng)稍等”，接著眉菱，你接通線路三迹栓，也告知他“請(qǐng)稍等”，最后俭缓，你接通線路四克伊，并與其通話。當(dāng)你結(jié)束了與線路四的通話之后华坦，你回過(guò)頭來(lái)接通線路三愿吹，當(dāng)你結(jié)束了與線路三的通話之后，你接通線路二惜姐，結(jié)束之后犁跪，你再接通線路一，當(dāng)與線路一的這位客戶結(jié)束通話后，你終于可以放下電話了坷衍。
這個(gè)例子中的每一通電話就像某函數(shù)中的一個(gè)遞歸調(diào)用撵颊。當(dāng)你接到一個(gè)電話且不能立即處理時(shí)，這個(gè)電話將被擱置惫叛；當(dāng)你有一個(gè)不需要立即觸發(fā)的函數(shù)調(diào)用時(shí)倡勇，它將停留在調(diào)用棧上。當(dāng)你可以接聽(tīng)一個(gè)電話時(shí)嘉涌，這個(gè)線路會(huì)被接通妻熊；當(dāng)你的代碼能夠觸發(fā)一個(gè)函數(shù)調(diào)用時(shí)，它會(huì)從調(diào)用棧中彈出仑最。在你看到之后的代碼案例有些發(fā)懵時(shí)扔役，請(qǐng)回想一下這個(gè)比喻。
數(shù)字的遞歸
每個(gè)遞歸函數(shù)都需要一個(gè)終止條件警医，從而使其不會(huì)無(wú)休止地循環(huán)下去亿胸。然而，僅僅加一個(gè)終止條件预皇，是不足以避免其無(wú)限循環(huán)的侈玄。該函數(shù)必須一步一步地接近終止條件。在遞歸步驟中吟温，問(wèn)題會(huì)逐步簡(jiǎn)化為更小的問(wèn)題序仙。
假設(shè)有一個(gè)函數(shù)：從1加到n。例如鲁豪，當(dāng)n = 4潘悼，它實(shí)現(xiàn)的就是“1 + 2 + 3 + 4”。
首先爬橡，我們需要尋找終止條件治唤。這一步可以認(rèn)為是找到那個(gè)不通過(guò)遞歸就直接結(jié)束該問(wèn)題的條件。當(dāng)n等于0時(shí)糙申，沒(méi)法再拆分了宾添，所以我們的遞歸在到達(dá)0時(shí)停止。
在每一步中郭宝，你將從當(dāng)前數(shù)字減去1辞槐。什么是遞歸條件？就是用減少的數(shù)字調(diào)用函數(shù)sum粘室。
function sum(num){
if (num === 0) {
return 0;
} else {
return num + sum(--num)
}
}
sum(4); //10
每一步過(guò)程如下：
- 執(zhí)行sum(4)榄檬。
- 4等于0么？否衔统，把sum(4)保留并執(zhí)行sum(3)鹿榜。
- 3等于0么海雪？否，把sum(3)保留并執(zhí)行sum(2)舱殿。
- 2等于0么奥裸？否，把sum(2)保留并執(zhí)行sum(1)沪袭。
- 1等于0么湾宙？否，把sum(1)保留并執(zhí)行sum(0)冈绊。
- 0等于0么侠鳄？是，計(jì)算sum(0)死宣。
- 提取sum(1)伟恶。
- 提取sum(2)。
- 提取sum(3)毅该。
- 提取sum(4)博秫。
這是查看函數(shù)如何處理每個(gè)調(diào)用的另一種方式：
sum(4)
4 + sum(3)
4 + ( 3 + sum(2) )
4 + ( 3 + ( 2 + sum(1) ))
4 + ( 3 + ( 2 + ( 1 + sum(0) )))
4 + ( 3 + ( 2 + ( 1 + 0 ) ))
4 + ( 3 + ( 2 + 1 ) )
4 + ( 3 + 3 )
4 + 6
10
我們可以發(fā)現(xiàn)，遞歸條件中的參數(shù)不斷改變眶掌，并逐漸接近并最終符合終止條件挡育。在上面的案例中，我們?cè)谶f歸條件中的每一步都將參數(shù)減1畏线，最后在終止條件中測(cè)試參數(shù)是否等于0静盅。
任務(wù)
- 使用常規(guī)循環(huán)方法而不是遞歸來(lái)寫(xiě)一個(gè)數(shù)字求和的sum函數(shù)。
- 寫(xiě)一個(gè)遞歸函數(shù)來(lái)實(shí)現(xiàn)兩數(shù)相乘寝殴。例如：
multiply(2,4)將返回8，寫(xiě)出multiply(2,4)的每一步發(fā)生的情況明垢。
數(shù)組的遞歸
數(shù)組的遞歸和數(shù)字的遞歸相似蚣常，類似于數(shù)字的遞減，我們?cè)诿恳徊竭f減數(shù)組中的元素個(gè)數(shù)痊银，直到獲得一個(gè)空數(shù)組抵蚊。
考慮使用數(shù)組作為求和函數(shù)的參數(shù)，并返回?cái)?shù)組中所有元素的總和溯革。求和函數(shù)如下：
function sum(arr) {
var len = arr.length;
if (len == 0) {
return 0;
} else {
return arr[0] + sum(arr.slice(1));
}
}
如果數(shù)組長(zhǎng)度等于0贞绳，則返回0，arr[0]表示數(shù)組的第一位致稀，arr.slice(1)表示從第一位開(kāi)始截取arr數(shù)組冈闭，并返回截取之后的數(shù)組。例如var arr = [1,2,3,4];抖单，arr[0]為1萎攒，arr.slice(1)為[2,3,4]遇八。當(dāng)我們執(zhí)行sum([1,2,3,4])時(shí)，都發(fā)生了一些什么耍休？
sum([1,2,3,4])
1 + sum([2,3,4])
1 + ( 2 + sum([3,4]) )
1 + ( 2 + ( 3 + sum([4]) ))
1 + ( 2 + ( 3 + ( 4 + sum([]) )))
1 + ( 2 + ( 3 + ( 4 + 0 ) ))
1 + ( 2 + ( 3 + 4 ) )
1 + ( 2 + 7 )
1 + 9
10
每一次執(zhí)行都檢查數(shù)組是否為空刃永，否則，對(duì)元素?cái)?shù)量逐漸遞減的該數(shù)組執(zhí)行遞歸羊精。
任務(wù)
- 使用常規(guī)循環(huán)方法而不是遞歸來(lái)寫(xiě)一個(gè)數(shù)組求和的sum函數(shù)斯够。
- 定義一個(gè)
length()函數(shù)，數(shù)組作為參數(shù)喧锦，返回?cái)?shù)組長(zhǎng)度（不可以使用Javascript Array對(duì)象內(nèi)置的length屬性）雳刺。例如：length(['a', 'b', 'c', 'd'])，并寫(xiě)出每一步發(fā)生的事情裸违。
總結(jié)
一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中有直接或間接調(diào)用自身的一種方法掖桦，它通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，遞歸策略只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算供汛，大大地減少了程序的代碼量枪汪。
本文只列舉兩個(gè)小案例，只為說(shuō)明遞歸是怎么回事怔昨，上述兩個(gè)案例的公式都是變量+函數(shù)的形式雀久，當(dāng)然也有很多函數(shù)+函數(shù)的形式的案例，例如文章開(kāi)頭提到的著名的斐波那契數(shù)列趁舀，代碼如下：
function func( n ) {
if (n == 0 || n == 1) {
return 1;
}
return func(n-1) + func(n-2);
}
下面來(lái)說(shuō)一下使用遞歸的步驟及優(yōu)缺點(diǎn)赖捌。
步驟
- 找規(guī)律，將這個(gè)規(guī)律轉(zhuǎn)換成一個(gè)公式return出來(lái)矮烹。
- 找出口越庇，出口即終止條件，它一定是一個(gè)已知的條件奉狈。
優(yōu)點(diǎn)
- 代碼異常簡(jiǎn)潔卤唉。
- 符合人類思維。
缺點(diǎn)
- 由于遞歸是調(diào)用函數(shù)自身仁期，而函數(shù)調(diào)用需要消耗時(shí)間和空間：每次調(diào)用桑驱，都要在內(nèi)存棧中分配空間以存儲(chǔ)參數(shù)、臨時(shí)變量、返回地址等，往棧中壓入和彈出數(shù)據(jù)都需要消耗時(shí)間往衷。這勢(shì)必導(dǎo)致執(zhí)行效率大打折扣斩个。
- 遞歸中的計(jì)算大都是重復(fù)的，其本質(zhì)是把一個(gè)問(wèn)題拆解成多個(gè)小問(wèn)題，小問(wèn)題之間存在互相重疊的部分，這樣的重復(fù)計(jì)算也會(huì)導(dǎo)致效率的低下。
- 調(diào)用椙看鳎可能會(huì)溢出亭螟。棧是有容量限制的，當(dāng)調(diào)用層次過(guò)多骑歹，就會(huì)超出棧的容量限制预烙，從而導(dǎo)致棧溢出！
可見(jiàn)遞歸的缺點(diǎn)還是很明顯的道媚，在實(shí)際開(kāi)發(fā)中扁掸，在可控的情況下，合理使用最域。
感謝您的閱讀谴分！
