第二十二章：遞迴關係

遞迴關係（Recurrence Relation）是演算法分析的核心工具。給定一個遞迴演算法，我們將其時間複雜度寫成遞迴式，再求解得到「閉合公式（closed form）」。

22.1 河內塔

河內塔問題：將 n 個圓盤從柱 A 移到柱 C（借助柱 B），每次只能移一個，且大盤不能放在小盤上。

遞迴關係：
T(1) = 1
T(n) = 2·T(n−1) + 1

閉合公式： T(n) = 2ⁿ − 1

展開過程：
T(n) = 2T(n-1) + 1
= 2(2T(n-2) + 1) + 1 = 4T(n-2) + 3
= 2ⁿ⁻¹·T(1) + 2ⁿ⁻¹ − 1
= 2ⁿ − 1

n = 64 時需要 2⁶⁴ − 1 ≈ 1.8 × 10¹⁹ 步。以每秒 10⁹ 步計算，需要約 5,849 億年（宇宙年齡 ≈ 138 億年）。

選擇圓盤數，觀察最少步數與遞迴移動過程。

圓盤數：

已執行步數

最少總步數 (2ⁿ−1)

等待開始

本步說明

合併排序（Merge Sort）將數組一分為二，分別遞迴排序後再合併。

遞迴關係：
T(1) = 1
T(n) = 2·T(n/2) + n　　（合併需要 O(n)）

n = 16 → T(n) =

遞迴樹：每層有 n 個工作量（合併），共 log₂n 層，故 T(n) = n·log₂n = Θ(n log n)。

形如 f(n) = c₁·f(n−1) + c₂·f(n−2) + ... + cₖ·f(n−k) 的遞迴稱為線性遞迴。

解法：特徵方程法（Characteristic Equation）

設 f(n) = rⁿ，代入得「特徵方程」：
rᵏ = c₁·rᵏ⁻¹ + c₂·rᵏ⁻² + ... + cₖ

若 k 個根 r₁, r₂, ..., rₖ 互不相同，通解為：
f(n) = A₁r₁ⁿ + A₂r₂ⁿ + ... + Aₖrₖⁿ

Fibonacci 數列：f(n) = f(n−1) + f(n−2)，特徵方程 r² = r + 1，兩根 φ = (1+√5)/2 ≈ 1.618、ψ = (1−√5)/2。

F(n) = (φⁿ − ψⁿ) / √5　　（Binet 公式）

分治演算法的遞迴式為 T(n) = a·T(n/b) + f(n)。輸入 a, b 和 f(n) 的形式，立即得出複雜度答案。

a（子問題個數，a ≥ 1）

b（問題縮小比例，b ≥ 2）

f(n) 的形式

常見演算法：
合併排序 → a=2, b=2, f=O(n)
二分搜尋 → a=1, b=2, f=O(1)
矩陣乘法(Strassen) → a=7, b=2, f=O(n²)

等待輸入...

主定理的三個 Case 對應三種情況：

Case 1（遞迴主導）：f(n) 增長比 n^(log_b a) 慢 → 遞迴樹的「葉節點」工作量主導，T(n) = Θ(n^(log_b a))
Case 2（均勡分擔）：f(n) ≈ n^(log_b a) → 每層工作量相等，多出 log n 倍，T(n) = Θ(n^(log_b a) · log n)
Case 3（合併主導）：f(n) 增長比 n^(log_b a) 快 → 根節點（合併）工作量主導，T(n) = Θ(f(n))

記憶訣竅：計算「分水嶺」c* = log_b(a)，看 f(n) 和 n^c* 誰增長更快：
f 更慢 → Case 1；f 相近 → Case 2；f 更快 → Case 3。

教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)