遞歸算法介紹

本節(jié)將主要介紹基礎(chǔ)算法中最為常見(jiàn)和最為簡(jiǎn)單的算法：遞歸算法。

1. 遞歸算法原理詳解

遞歸算法，通常是把一個(gè)大型復(fù)雜的問(wèn)題，一次次通過(guò)遞歸調(diào)用而層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，基本思想是將大問(wèn)題一步步化為小問(wèn)題，遞歸算法只需少量的程序就可表達(dá)對(duì)大問(wèn)題的計(jì)算過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了程序代碼。從代碼的角度上來(lái)看就是函數(shù)調(diào)用自身，我們稱之為遞歸。

2. 舉例說(shuō)明遞歸算法

我們現(xiàn)在用一個(gè)簡(jiǎn)單的例子進(jìn)行說(shuō)明：假設(shè)我們需要寫(xiě)一個(gè)函數(shù)去求數(shù)字n的階乘。當(dāng)輸入5時(shí)，輸出5!=120，當(dāng)輸入6時(shí)，輸出6!=720。如果我們編寫(xiě)了一個(gè)函數(shù) F(n) 用來(lái)求解輸入?yún)?shù) n 的階乘值，很明顯我們可以發(fā)現(xiàn)這樣一個(gè)遞歸關(guān)系：F(n) = n * F(n - 1)，那么我們求解 F(n) 的代碼可以這樣寫(xiě)：

遞歸求 5 的階乘 Python 實(shí)現(xiàn)

def F(n):
    if n == 1:
        return 1
    return n * F(n - 1)

前兩行的語(yǔ)句是遞歸終止條件，這個(gè)是必須要有的，而且必須是遞歸要能到達(dá)的。最后一個(gè) n * F(n - 1) 正是遞歸調(diào)用自身，且每次遞歸的參數(shù)都會(huì)減少直到最后的終止條件結(jié)束。我們用示例圖來(lái)演示下 F(5) 執(zhí)行的遞歸過(guò)程，這樣方便我們理解遞歸調(diào)用。

遞歸算法動(dòng)態(tài)示意圖：

從上面的示意圖可以看到，遞歸的思想就是在不停調(diào)用本身往下執(zhí)行，直到終止條件達(dá)到然后再回推結(jié)果。遞歸帶來(lái)的好處非常明顯，就是減少代碼，讓代碼看起來(lái)簡(jiǎn)潔明了。假如我們要使用非遞歸算法來(lái)求解 n 的階乘，代碼如下：

def F_no_recursive(n):
    s = 1
    for i in range(1, n + 1):
        s = s * i
    return s

可以看到，遞歸代碼相比不使用遞歸的代碼少了 for 循環(huán)，并且遞歸的代碼看起來(lái)會(huì)比較簡(jiǎn)潔和清楚，這在二叉樹(shù)的問(wèn)題中會(huì)體現(xiàn)的非常明顯。

3. 函數(shù)調(diào)用過(guò)程

在所有的編程語(yǔ)言中，函數(shù)的調(diào)用都是這樣的過(guò)程：

• 將當(dāng)前調(diào)用函數(shù)的下一個(gè)指令地址壓入堆棧，并保存現(xiàn)場(chǎng)環(huán)境；
• 調(diào)到調(diào)用函數(shù)地址去執(zhí)行；
• 調(diào)用函數(shù)執(zhí)行完成后，調(diào)用 ret 指令彈出下一步執(zhí)行的地址，返回到原來(lái)的函數(shù)中接著執(zhí)行下一條語(yǔ)句。

示意圖如下：

自己調(diào)用也是一樣的過(guò)程，并不會(huì)說(shuō)自己調(diào)用自己遞歸就會(huì)在函數(shù)內(nèi)部執(zhí)行，同樣是在另一個(gè)地址有一份相同的函數(shù)代碼拷貝，也就是將上圖中的函數(shù) B() 換成函數(shù) A()，這幅圖同樣正確。遞歸調(diào)用的示意圖如下：

4. 遞歸算法的缺點(diǎn)

前面說(shuō)到了遞歸問(wèn)題的優(yōu)點(diǎn)，就是使用遞歸后整體代碼簡(jiǎn)潔明了，閱讀起來(lái)讓人如沐春風(fēng)。但是遞歸方法也會(huì)才能在較大問(wèn)題：

• 遞歸太深，容易導(dǎo)致棧溢出異常。前面介紹過(guò)，函數(shù)調(diào)用是通過(guò)棧（stack）這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，每當(dāng)進(jìn)入一個(gè)函數(shù)調(diào)用，棧就會(huì)加一層棧幀，每當(dāng)函數(shù)返回，棧就會(huì)減一層棧幀。由于棧的大小不是無(wú)限的，所以，遞歸調(diào)用的次數(shù)過(guò)多，會(huì)導(dǎo)致棧溢出；
• 可能存在大量的冗余計(jì)算，算法的時(shí)間復(fù)雜度呈指數(shù)級(jí)增長(zhǎng)，這個(gè)會(huì)在后面的遞歸實(shí)例中展示。

5. 解決遞歸問(wèn)題的通用思路

對(duì)于一個(gè)遞歸問(wèn)題，我們會(huì)有一套模板去實(shí)現(xiàn)這樣一個(gè)遞歸算法：

• 遞歸終止條件：一定和必須要有；
• 遞歸公式：遞歸的核心，找不出遞歸公式的，也就無(wú)法使用遞歸算法來(lái)解決。這里實(shí)現(xiàn)遞歸算法的遞部分；
• 返回預(yù)定結(jié)果：返回我們預(yù)先定好的結(jié)果參與遞歸算法的歸部分；

基本上完成這樣三個(gè)步驟，一個(gè)簡(jiǎn)易的遞歸算法也就算完成了，剩下的就是按照這三部實(shí)現(xiàn)代碼了。我們不妨用前面的遞歸函數(shù)來(lái)看看這三步的具體位置：

在下一節(jié)中，我們會(huì)在 LeetCode 上完成 3 道和遞歸相關(guān)的算法題，并使用這三個(gè)步驟去完成相關(guān)題解，也會(huì)讓大家加深對(duì)這三步的理解。

6. 小結(jié)

本節(jié)在介紹了遞歸算法概念并對(duì)遞歸算法的優(yōu)缺點(diǎn)進(jìn)行了相關(guān)分析，緊接著用 leetcode 上的兩道基礎(chǔ)遞歸題目進(jìn)行了練習(xí)和說(shuō)明，幫助理解遞歸算法。

Tips：文中動(dòng)圖制作參考：https://visualgo.net/zh/sorting。