遞歸算法介紹

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

1. 遞歸算法原理詳解

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

2. 舉例說明遞歸算法

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

遞歸求 5 的階乘 Python 實現

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

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

遞歸算法動態示意圖：

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

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

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

3. 函數調用過程

在所有的編程語言中，函數的調用都是這樣的過程：

• 將當前調用函數的下一個指令地址壓入堆棧，并保存現場環境；
• 調到調用函數地址去執行；
• 調用函數執行完成后，調用 ret 指令彈出下一步執行的地址，返回到原來的函數中接著執行下一條語句。

示意圖如下：

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

4. 遞歸算法的缺點

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

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

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

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

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

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

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

6. 小結

本節在介紹了遞歸算法概念并對遞歸算法的優缺點進行了相關分析，緊接著用 leetcode 上的兩道基礎遞歸題目進行了練習和說明，幫助理解遞歸算法。

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