遞歸算法介紹

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

1. 遞歸算法原理詳解

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

2. 舉例說明遞歸算法

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

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

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

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

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

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

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

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

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

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

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

示意圖如下：

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

4. 遞歸算法的缺點

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

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

5. 解決遞歸問題的通用思路

對于一個遞歸問題，我們會有一套模板去實現(xiàn)這樣一個遞歸算法：

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

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

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

6. 小結(jié)

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

Tips：文中動圖制作參考：https://visualgo.net/zh/sorting。