從遞推到遞歸#

遞推是人類本能的正向思維——從 1 數到 100、從小到大、由易到難。數學歸納法也是遞推的思維方式：假定規律對 N 成立，只要證明對 N+1 也成立，就能推廣到所有自然數。

遞歸則是完全相反的逆向思維。以計算 5! 為例：

  • 遞推方式：1 x 2 x 3 x 4 x 5 = 120
  • 遞歸方式：5! = 5 x 4!，而 4! = 4 x 3!，…，直到 1! = 1，再倒推回所有結果

遞歸的兩個明顯妙處：

  1. 只需解決當前一步的問題，就能解決全部問題（例如計算 N!，只要關心 N 乘以某一個數即可）
  2. 複製同一個過程即可——每一個問題在形式上都相同，否則無法通過同一個過程完成不同階段的計算

2.1.1 看似簡單的遞推公式#

例題 2.1：搶 20 遊戲#

  • 兩人輪流從 1 和 2 中選一個數字，在對方基礎上加 1 或 2，誰先加到 20 就贏
  • 遞推方式（從小到大）：列舉各種情況，越到後面越複雜
  • 遞歸方式（倒過來想）：要搶到 20，就要先搶到 17；要搶到 17，就要先搶到 14……以此類推
  • 核心規律：控制每一輪兩人喊出的數字總和為 3，就能牢牢控制整個過程

例題 2.2：上台階問題（斐波那契數列）#

  • 從 1 開始加到 20，每次可以加 1 或 2，有多少種不同的方法？
  • 用遞歸的思路：走到第 20 級，前一步只可能從第 18 級或第 19 級跳來
  • 因此 F(20) = F(18) + F(19)，遞歸公式為 F(n) = F(n-1) + F(n-2)
  • 結束條件：F(1) = 1，F(2) = 2
  • 這就是著名的斐波那契數列，其中 F(20) = 10946

很多等價問題的解都是斐波那契數列。如果發現某個問題等價於一個長期未解的問題，最好放一放——事實上所有 NP 完全問題都是等價的。

2.1.2 漢諾塔和九連環：用遞歸表述的問題#

例題 2.3：漢諾塔問題#

  • 三根柱子 A、B、T，A 柱上疊著 64 個大小不同的盤子（小的在上），目標是全部移到 B 柱
  • 規則：每次只移一個盤子；小盤子不能放在大盤子下面；T 柱可做中轉
  • 遞歸解法（以 64 個盤子為例）：
    1. 先把上面 63 個盤子從 A 移到 T（用 B 做中轉）
    2. 把最底下的第 64 個盤子從 A 移到 B
    3. 再把 T 上的 63 個盤子移到 B（用 A 做中轉）
  • 移動次數的遞推公式：S(64) = 2S(63) + 1，即 S(64) = 2^64 - 1 ≈ 1.8 x 10^19
void Hanoi(n, source, target, auxiliary) {
    if (n > 0) {
        Hanoi(n-1, source, auxiliary, target);
        MoveTop(source, target);
        Hanoi(n-1, auxiliary, target, source);
    }
}

遞歸代碼簡單的原因是自己調用了自己。這在現實世界裡很難想像，但在計算機的世界裡非常普遍。

九連環#

  • 漢諾塔的等價問題，拆解九連環的原理完全一樣
  • 九個環的操作步驟是 2^9 - 1 = 511 次，不到 10 分鐘就能完成

2.1.3 難倒高斯的八皇后問題#

例題 2.4：八皇后問題#

  • 在 8x8 棋盤上擺放 8 個皇后，使其不互相攻擊（不在同一行、同一列或同一斜線）
  • 大數學家高斯窮其一生只找到 76 種方案，全部方案是 92 種
  • 遞推方式的困難：從第 1 行開始逐行擺放，組合了 7、8 層的邏輯極為複雜
  • 遞歸解法：
    1. 假設前 7 行已擺好 7 個皇后（位置是否正確暫不管）
    2. 在第 8 行逐一試驗，找到不衝突的位置
    3. 如果找不到，回溯調整第 7 個皇后的位置
    4. 如果第 7 個也找不到合適位置，繼續回溯到第 6 個，以此類推

遞歸算法的好處在於：不需要總結普遍規律，只需搞清楚如何拆解問題即可。代碼在邏輯上都非常簡潔，只要定義最頂層的邏輯，下面一層層的邏輯不過是自動複製頂層邏輯而已。

要點回顧#

  • 人的思維通常是遞推（由小到大），計算思維通常是遞歸（自頂向下）
  • 遞歸的核心：先把簡單的問題搞清楚，看看能否找到規律，再用於複雜問題
  • 先把大問題分解為小問題，小問題和大問題有相同的結構和解決辦法