dan-freeman-401296-unsplash.jpg

簡介

使用遞歸可以更自然地解決一些問題。例如，像斐波那契數(shù)列：數(shù)列中的每個數(shù)字都是數(shù)列中前兩個數(shù)字的和。凡是需要您構(gòu)建或遍歷樹狀數(shù)據(jù)結(jié)構(gòu)的問題基本都可以通過遞歸來解決，鍛煉自己強(qiáng)大的遞歸思維，你會發(fā)現(xiàn)解決這類問題十分容易。

在本文中，我將列舉兩個案例，讓你們了解遞歸函數(shù)是如何工作的。

綱要

• 什么是遞歸
• 數(shù)字的遞歸
• 數(shù)組的遞歸
• 總結(jié)

什么是遞歸

函數(shù)的遞歸就是在函數(shù)中調(diào)用自身，看一個簡單的例子：

function doA(n) {
    ...
    doA(n-1);
}

為了理解遞歸在理論上是如何工作的，我們先舉一個與代碼無關(guān)的例子。想象一下，你是一家公司的話務(wù)員。由于這是一家業(yè)務(wù)繁忙的公司，你的座機(jī)連接多條線路，因此你可以同時處理多個電話。每條線路對應(yīng)接收器上的一個按鈕，當(dāng)有來電時，該按鈕將閃爍。今天當(dāng)你到達(dá)公司開始工作時，發(fā)現(xiàn)有四條線路對應(yīng)的按鈕正在閃爍，所以你需要接聽所有這些電話。

你接通線路一，并告訴他“請稍等”，然后你接通線路二，并告訴他“請稍等”，接著，你接通線路三，也告知他“請稍等”，最后，你接通線路四，并與其通話。當(dāng)你結(jié)束了與線路四的通話之后，你回過頭來接通線路三，當(dāng)你結(jié)束了與線路三的通話之后，你接通線路二，結(jié)束之后，你再接通線路一，當(dāng)與線路一的這位客戶結(jié)束通話后，你終于可以放下電話了。

這個例子中的每一通電話就像某函數(shù)中的一個遞歸調(diào)用。當(dāng)你接到一個電話且不能立即處理時，這個電話將被擱置；當(dāng)你有一個不需要立即觸發(fā)的函數(shù)調(diào)用時，它將停留在調(diào)用棧上。當(dāng)你可以接聽一個電話時，這個線路會被接通；當(dāng)你的代碼能夠觸發(fā)一個函數(shù)調(diào)用時，它會從調(diào)用棧中彈出。在你看到之后的代碼案例有些發(fā)懵時，請回想一下這個比喻。

數(shù)字的遞歸

每個遞歸函數(shù)都需要一個終止條件，從而使其不會無休止地循環(huán)下去。然而，僅僅加一個終止條件，是不足以避免其無限循環(huán)的。該函數(shù)必須一步一步地接近終止條件。在遞歸步驟中，問題會逐步簡化為更小的問題。

假設(shè)有一個函數(shù)：從1加到n。例如，當(dāng)n = 4，它實(shí)現(xiàn)的就是“1 + 2 + 3 + 4”。

首先，我們需要尋找終止條件。這一步可以認(rèn)為是找到那個不通過遞歸就直接結(jié)束該問題的條件。當(dāng)n等于0時，沒法再拆分了，所以我們的遞歸在到達(dá)0時停止。

在每一步中，你將從當(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

每一步過程如下：

• 執(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ù)如何處理每個調(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ù)不斷改變，并逐漸接近并最終符合終止條件。在上面的案例中，我們在遞歸條件中的每一步都將參數(shù)減1，最后在終止條件中測試參數(shù)是否等于0。

任務(wù)

1. 使用常規(guī)循環(huán)方法而不是遞歸來寫一個數(shù)字求和的sum函數(shù)。
2. 寫一個遞歸函數(shù)來實(shí)現(xiàn)兩數(shù)相乘。例如：multiply(2,4) 將返回8，寫出multiply(2,4)的每一步發(fā)生的情況。

數(shù)組的遞歸

數(shù)組的遞歸和數(shù)字的遞歸相似，類似于數(shù)字的遞減，我們在每一步遞減數(shù)組中的元素個數(shù)，直到獲得一個空數(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ù)組長度等于0，則返回0，arr[0]表示數(shù)組的第一位，arr.slice(1)表示從第一位開始截取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])時，都發(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ù)組是否為空，否則，對元素?cái)?shù)量逐漸遞減的該數(shù)組執(zhí)行遞歸。

任務(wù)

1. 使用常規(guī)循環(huán)方法而不是遞歸來寫一個數(shù)組求和的sum函數(shù)。
2. 定義一個length()函數(shù)，數(shù)組作為參數(shù)，返回?cái)?shù)組長度（不可以使用Javascript Array對象內(nèi)置的length屬性）。例如：length(['a', 'b', 'c', 'd'])，并寫出每一步發(fā)生的事情。

總結(jié)

一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。

本文只列舉兩個小案例，只為說明遞歸是怎么回事，上述兩個案例的公式都是變量+函數(shù)的形式，當(dāng)然也有很多函數(shù)+函數(shù)的形式的案例，例如文章開頭提到的著名的斐波那契數(shù)列，代碼如下：

function func( n ) { 
    if (n == 0 || n == 1) {
        return 1;
    }
        return func(n-1) + func(n-2);
}
    

下面來說一下使用遞歸的步驟及優(yōu)缺點(diǎn)。

步驟

1. 找規(guī)律，將這個規(guī)律轉(zhuǎn)換成一個公式return出來。
2. 找出口，出口即終止條件，它一定是一個已知的條件。

優(yōu)點(diǎn)

1. 代碼異常簡潔。
2. 符合人類思維。

缺點(diǎn)

1. 由于遞歸是調(diào)用函數(shù)自身，而函數(shù)調(diào)用需要消耗時間和空間：每次調(diào)用，都要在內(nèi)存棧中分配空間以存儲參數(shù)、臨時變量、返回地址等，往棧中壓入和彈出數(shù)據(jù)都需要消耗時間。這勢必導(dǎo)致執(zhí)行效率大打折扣。
2. 遞歸中的計(jì)算大都是重復(fù)的，其本質(zhì)是把一個問題拆解成多個小問題，小問題之間存在互相重疊的部分，這樣的重復(fù)計(jì)算也會導(dǎo)致效率的低下。
3. 調(diào)用?？赡軙绯觥Ｊ怯腥萘肯拗频?，當(dāng)調(diào)用層次過多，就會超出棧的容量限制，從而導(dǎo)致棧溢出！

可見遞歸的缺點(diǎn)還是很明顯的，在實(shí)際開發(fā)中，在可控的情況下，合理使用。

感謝您的閱讀！