跳轉到

04.1 遞迴關係：從 Fibonacci 到漢諾塔的解構#

把大問題拆成自己：遞迴的思想史#

「要解決規模 \(n\) 的問題，先解決規模較小的同型問題」——這種思維在數學史上有兩個著名源頭：

  1. 1202 年，Fibonacci 的 Liber Abaci：兔子問題寫下第一條廣為人知的遞迴關係 \(F_n = F_{n-1} + F_{n-2}\) 。有趣的是，Fibonacci 本人並沒有「遞迴」的抽象概念——他只是逐年列表記錄；「遞迴數列」作為數學物件的意識，要到三個多世紀後才形成。
  2. 1883 年，法國數學家 Édouard Lucas 發明「漢諾塔」遊戲：他編造了婆羅門神廟中 64 金盤移動的傳說，並立刻指出其數學本質。漢諾塔不只是玩具——它是分治演算法（divide and conquer）的原型，是電腦科學教科書講解遞迴的第一個例子，也是圖同構搜尋與狀態空間思想的先聲。

遞迴關係（recurrence relation）的正式定義：以較小指標的項定義第 \(n\) 項的方程。它與前一節的 Pascal 恆等式一脈相承，並直接通往下一節的生成函數與本章末的演算法複雜度。

漢諾塔：最小的分治範例#

問題#

三根柱子， \(n\) 個大小相異的盤子疊在第一柱（大在下）。規則：每次移動一盤，大盤不得壓小盤。求把全部盤子移到第三柱的最少移動次數 \(T_n\) 。

遞迴建立#

要把 \(n\) 盤移到第三柱，必須先讓最大盤可動，即先把上面 \(n-1\) 盤移到第二柱（ \(T_{n-1}\) 次），移大盤（1 次），再把 \(n-1\) 盤從第二柱移到第三柱（ \(T_{n-1}\) 次）：

\[T_1 = 1, \qquad T_n = 2T_{n-1} + 1.\]

定理#

\[T_n = 2^n - 1.\]

證明一（歸納）： \(T_1 = 1 = 2^1 - 1\) 。設 \(T_{n-1} = 2^{n-1} - 1\) ，則 \(T_n = 2(2^{n-1} - 1) + 1 = 2^n - 1\) 。 \(\blacksquare\)

證明二（不動點技巧）：在遞迴式兩邊加 1： \(T_n + 1 = 2(T_{n-1} + 1)\) 。令 \(S_n = T_n + 1\) ，則 \(S_n = 2S_{n-1}\) ，是純等比數列， \(S_n = 2^{n-1} S_1 = 2^n\) ，故 \(T_n = 2^n - 1\) 。 \(\blacksquare\)

下界論證（最少性）：遞迴的每一步都是被迫的（最大盤若非最後一個移動步驟的核心，其上 \(n-1\) 盤必須先清空到唯一可用柱），故 \(T_n = 2^n - 1\) 同時是上界與下界——遞迴論證天然兼具兩面，這是它相對窮舉法的優勢。

傳說的檢驗： \(T_{64} = 2^{64} - 1 \approx 1.84 \times 10^{19}\) ；若每秒移一盤，需五千八百多億年——遠超宇宙年齡（約 \(1.38 \times 10^{10}\) 年）。Lucas 的傳說在數學上「成立」：末日確實遙遠。

def hanoi(n, src, aux, dst, moves):
    if n == 1:
        moves.append((src, dst)); return
    hanoi(n-1, src, dst, aux, moves)
    moves.append((src, dst))
    hanoi(n-1, aux, src, dst, moves)

for n in range(1, 11):
    moves = []
    hanoi(n, "A", "B", "C", moves)
    assert len(moves) == 2**n - 1
print("漢諾塔：移動次數 = 2^n - 1，驗證通過")

遞迴程式與遞迴關係同構：程式碼就是遞迴式的可執行版本。這種對應是離散數學與程式設計之間最重要的橋樑之一（04.3 節將量化其代價）。

Fibonacci 與線性齊次遞迴#

定義（ \(k\) 階線性齊次遞迴）#

\[a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}, \quad c_k \ne 0,\]

配合初始條件 \(a_0, \dots, a_{k-1}\) 。

定理（特徵方程法）#

設對應特徵方程 \(x^k = c_1 x^{k-1} + \cdots + c_k\) 有 \(k\) 個相異根 \(r_1, \dots, r_k\) ，則通解為

\[a_n = A_1 r_1^n + \cdots + A_k r_k^n,\]

係數由初始條件聯立解出。

證明：每個 \(r_i^n\) 代入遞迴式檢驗：因 \(r_i\) 是特徵方程的根， \(r_i^n = c_1 r_i^{n-1} + \cdots + c_k r_i^{n-k}\) ，故 \(r_i^n\) 是解；線性組合仍是解（遞迴是線性的）。通解空間是 \(k\) 維向量空間（初始條件與解一一對應），而 \(k\) 個相異指數函數線性獨立，故窮盡所有解。 \(\blacksquare\)

應用：Fibonacci 封閉式（Binet 公式）#

特徵方程 \(x^2 = x + 1\) ，根 \(\varphi = \frac{1+\sqrt5}{2}\) （黃金比）與 \(\psi = \frac{1-\sqrt5}{2}\) 。由 \(F_0=0, F_1=1\) 解得：

\[F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}.\]

深意： \(\psi \approx -0.618\) ， \(|\psi| < 1\) ，故 \(F_n \approx \varphi^n/\sqrt5\) ——Fibonacci 數是指數增長的，增長率恰為黃金比 \(\varphi \approx 1.618\) 。這解釋了為什麼第 50 個 Fibonacci 數就超過 120 億：生物族群、演算法分支，凡合此遞迴者皆爆炸性增長。

重根情況：若 \(r\) 為 \(m\) 重根，則 \(r^n, nr^n, \dots, n^{m-1}r^n\) 皆為解（可代入驗證，理論由線性代數的 Jordan 形給出）。

非齊次遞迴與迭代法#

漢諾塔的 \(T_n = 2T_{n-1} + 1\) 含非常數項。標準做法：齊次化—— \(T_n - T_{n-1} = 2(T_{n-1} - T_{n-2})\) ，令 \(S_n = T_n - T_{n-1}\) ，得純等比，疊加即得封閉式。另一條更通用的路是迭代/展開：

\[T_n = 2T_{n-1} + 1 = 4T_{n-2} + 2 + 1 = \cdots = 2^n T_0 + (2^n - 1) = 2^n - 1.\]

範例：Chebyshev 型的應用——分治遞迴預告#

合併排序的複雜度滿足

\[W(n) = 2W(n/2) + n - 1, \qquad W(1) = 0.\]

迭代展開： \(W(n) = 4W(n/4) + 2(n/2 - 1) + (n-1) = \cdots = n \log_2 n - n + 1\) 。這個形如 \(T(n) = aT(n/b) + f(n)\) 的遞迴，其一般解法就是電腦科學的 Master 定理——我們在 04.3 節以離散方法（展開樹）推導它。此處的關鍵訊息：遞迴關係是演算法分析的文法。

病態案例：不含 11 的序列#

數長度 \(n\) 、不含相鄰兩個 1 的 0-1 序列數 \(A_n\) ：按結尾分類——結尾 0 則前面任意（ \(A_{n-1}\) ），結尾 1 則倒數第二必為 0（ \(A_{n-2}\) ）：

\[A_n = A_{n-1} + A_{n-2}, \quad A_0 = 1, A_1 = 2.\]

這就是 Fibonacci！03.2 節用組合求和 \(\sum_k \binom{n-k}{k}\) 得到同一數列——雙重證明給出恆等式 \(\sum_k \binom{n-k}{k} = F_{n+1}\) ：一個數，兩條路，恆等式由「同數二算」自動成立。這是組合學最重要的證明哲學之一。

遞迴的理論深度一瞥：從 Lucas 到圖靈#

遞迴思想在二十世紀發生兩次質變：

  1. 1920 年代，Ackermann 函數：一個雙重遞迴（參數遞迴套遞迴）的函數，增長快過任何原始遞迴函數——它證明「遞迴」內部還有層級，直接影響了可計算性理論的誕生。
  2. 1936 年，圖靈機：把「機械地由前態定義後態」推到極致，成為通用計算的形式模型；今日所有程式語言都內建遞迴（呼叫棧）。

遞迴同時是威力（分治、動態規劃）與陷阱（指數爆炸、棧溢出）的來源： naive 的 Fibonacci 遞迴是 \(O(\varphi^n)\) ，而動態規劃（記憶化）把它壓到 \(O(n)\) ——差別只在「是否重複計算」。這一課將在 04.3 節量化。

from functools import lru_cache
import time

# 病態版：指數時間
def fib_slow(n):
    return n if n < 2 else fib_slow(n-1) + fib_slow(n-2)

# 修復版：記憶化 → 線性時間
@lru_cache(maxsize=None)
def fib_fast(n):
    return n if n < 2 else fib_fast(n-1) + fib_fast(n-2)

t0 = time.perf_counter(); fib_slow(30); t1 = time.perf_counter()
t2 = time.perf_counter(); fib_fast(30); t3 = time.perf_counter()
print(f"n=30: naive {t1-t0:.4f}s, memoized {t3-t2:.6f}s")
# 典型輸出：naive 約 0.15s，memoized 約 0.00002s —— 差 4 個數量級

章末小結#

  • 遞迴三步驟：找初始條件、按「最後一步」分類建立遞迴式、求解（封閉式或漸近）。
  • 漢諾塔 \(T_n = 2T_{n-1} + 1 \Rightarrow 2^n - 1\) ，是分治與遞迴程式的原型。
  • 線性齊次遞迴用特徵方程化為代數問題；Fibonacci 的 Binet 公式揭示黃金比增長。
  • 「同數二算」：遞迴證明與組合證明互相鎖定恆等式。
  • 遞迴是演算法分析的文法（分治遞迴、Master 定理前奏），也是可計算性理論的源頭。

下一步#

遞迴式能「解」的秘訣，藏在把數列看成多項式的係數這個視角裡： \(F_0 + F_1 x + F_2 x^2 + \cdots\) 竟然是 \(\frac{x}{1-x-x^2}\) 。下一節「04.2 生成函數」將展示：把無窮數列壓進一個有理函數後，遞迴式變成代數方程、捲積變成乘法——Euler 為整數分拆發明的這門「魔法」，至今是組合學與演算法分析的主力工具。