遞迴（進階）

你怎麼證明一段遞迴「一定會停」？

入門篇裡我們學會：遞迴要有基底情形(base case)、要有遞迴情形(recursive case)，而且每次呼叫要「朝基底前進」。聽起來很合理，但這句「朝基底前進」其實藏著一個深刻的問題——你怎麼確定它真的會停？

考慮一個看似無害的函式：

def collatz_steps(n):
    if n == 1:
        return 0
    if n % 2 == 0:
        return 1 + collatz_steps(n // 2)      # 偶數減半
    return 1 + collatz_steps(3 * n + 1)        # 奇數變 3n+1

它有基底情形（n == 1），每次也都在「做事」。但 3 * n + 1 明明把問題變大了。這支函式到底會不會停？答案是：沒有人知道。這就是著名的考拉茲猜想(Collatz conjecture)，至今未解。一段語法上完全合法、邏輯上看似正常的遞迴，可能根本無法被證明會終止。

入門篇教你「寫對」遞迴；進階篇要教你看穿遞迴。我們會建立終止性的嚴謹判準、把遞迴與數學歸納法接上、學會在系統堆疊撐不住時親手把遞迴攤平成迴圈，最後走進相互遞迴、回溯剪枝，以及那個成長速度快到無法用迴圈表達的怪物——Ackermann 函式。這篇假設你已經熟悉呼叫堆疊、記憶化與河內塔；我們不再重述，直接往更深處挖。

良基遞迴：終止性的嚴謹判準

「朝基底前進」要怎麼形式化？關鍵概念叫做良基關係(well-founded relation)。直覺是這樣：如果你能找到一個從「問題狀態」映到某個不存在無限遞減鏈的集合的量，而且每次遞迴呼叫都讓這個量嚴格下降，那麼遞迴就保證終止。這個量稱為遞減度量(decreasing measure)或變異函數(variant)。

自然數集 $\mathbb{N}$ 配上「小於」就是最典型的良基集合：你不可能從任何自然數出發，一直嚴格遞減卻永不停止（因為下面卡著 $0$）。所以只要證明「每次遞迴，某個自然數度量嚴格變小」，終止性就成立。

回看階乘 factorial(n)：度量就是 n 本身，每次呼叫 n → n-1 嚴格遞減，且不會低於 $0$。終止。再看河內塔 hanoi(n, ...)：度量是盤數 n，每次 n → n-1，終止。

度量不一定要是單一變數。考慮在二維格點上往左下角走的遞迴：

def paths(x, y):
    if x == 0 or y == 0:
        return 1
    return paths(x - 1, y) + paths(x, y - 1)

這裡 x 或 y 有時不變，但 x + y 每次必定嚴格遞減。所以度量取 x + y 就能證明終止。當單一變數不夠用時，常用的還有字典序(lexicographic order)：先比第一個分量，相同再比第二個——這正是 Ackermann 函式終止的關鍵，稍後會看到。

觀念校正：「有基底情形」不等於「會終止」。考拉茲那支函式有基底情形卻可能不終止；真正保證終止的，是「存在一個在良基集合中嚴格遞減的度量」。寫遞迴時，請養成習慣在心裡（或註解裡）寫下那個度量是什麼。

遞迴與歸納法：同一枚硬幣的兩面

良基遞迴之所以重要，是因為它和數學歸納法(mathematical induction)是嚴格對偶的。這不是比喻，而是邏輯上的等價。

• 歸納法證明「對所有 $n$，性質 $P(n)$ 成立」：先證基底 $P(0)$，再證「若 $P(k)$ 成立則 $P(k+1)$ 成立」。
• 遞迴計算「對所有 $n$ 的答案」：先給基底答案 $f(0)$，再給「由 $f(k)$ 推出 $f(k+1)$」的規則。

兩者的結構一模一樣：基底情形對應歸納基礎，遞迴情形對應歸納步驟。這帶來一個極實用的後果——你可以用歸納法證明遞迴函式的正確性。

看一個例子：證明階乘真的算出 $n!$

我們宣稱 factorial(n) 對所有 $n \ge 0$ 回傳 $n!$。用歸納法：

• 基底：$n = 0$ 時函式回傳 1，而 $0! = 1$。成立。
• 歸納假設：假設 factorial(k) 正確回傳 $k!$。
• 歸納步驟：factorial(k+1) 回傳 (k+1) * factorial(k)，依假設即 $(k+1) \times k! = (k+1)!$。成立。

由歸納法，對所有 $n \ge 0$ 函式正確。注意這個證明的形狀完全跟著程式碼的形狀走：基底情形對基底，遞迴呼叫對歸納假設。這正是遞迴程式可讀、可證的根本原因——它的正確性論證是「免費附贈」的。

當遞迴呼叫的參數不是 n-1 而是「任意更小的值」（例如費氏的 fib(n-1) 與 fib(n-2)），就要改用強歸納法(strong induction)：假設對「所有小於 $n$ 的值」都成立，再推 $n$。良基遞迴的一般理論，本質上就是強歸納法的計算版本。

把遞迴親手攤平成迴圈

入門篇提過：遞迴太深會堆疊溢位(stack overflow)，這時往往要改寫成迭代。但很多人卡在「分岔遞迴（樹狀）怎麼改？」進階的答案是：用一個明確的堆疊(explicit stack)，親手模擬系統幫你做的事。

系統的呼叫堆疊不是魔法，它只是一個 LIFO 容器。我們完全可以拿一個 list 當堆疊，自己 push／pop，把遞迴的展開與回捲一步步重現。

動手算一下：用顯式堆疊做樹的前序走訪

先看自然的遞迴版（二元樹前序走訪）：

def preorder_rec(node, out):
    if node is None:
        return
    out.append(node.val)         # 先訪根
    preorder_rec(node.left, out)  # 再左
    preorder_rec(node.right, out) # 最後右

改成顯式堆疊。注意一個細節：堆疊是 LIFO，我們希望「左子樹先被處理」，所以要先 push 右、後 push 左，這樣 pop 時左才會先出來：

def preorder_iter(root):
    out = []
    if root is None:
        return out
    stack = [root]
    while stack:
        node = stack.pop()        # 取出待處理節點
        out.append(node.val)
        if node.right is not None:
            stack.append(node.right)  # 後出，故先壓
        if node.left is not None:
            stack.append(node.left)   # 先出，故後壓
    return out

這兩版輸出完全相同，但迭代版的「堆疊」放在堆積區(heap)（list 是動態配置的物件），不受系統呼叫堆疊深度上限（CPython 預設約 1000 層）的束縛。一棵深達數十萬層的退化樹（其實是一條鏈），遞迴版會 RecursionError，迭代版卻能從容走完。

這個技巧的威力在於它通用：任何遞迴都能機械化地轉成「顯式堆疊 + 狀態機」。後序走訪稍微麻煩（需記錄「左右子樹是否已展開」的狀態），但原理一致——你只是把編譯器原本替你管理的返回位址與區域狀態，搬到自己手上管理。理解這一點，你就不再害怕「遞迴改迭代」這類面試常見題。

線性、樹狀、相互、巢狀：遞迴的形狀學

入門篇看過線性遞迴（階乘）與樹狀遞迴（費氏）。進階要補上兩種更微妙的形狀。

相互遞迴(mutual recursion)：兩個函式互相呼叫，誰也不直接呼叫自己。判斷奇偶就是乾淨的例子：

def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)     # 偶數的前一個是奇數

def is_odd(n):
    if n == 0:
        return False
    return is_even(n - 1)    # 奇數的前一個是偶數

度量同樣是 n，每跨一次呼叫就遞減 $1$，所以終止。相互遞迴在剖析器(parser)裡無所不在：「運算式呼叫項、項呼叫因子、因子又可能括回運算式」，這種互相纏繞的結構（遞迴下降剖析, recursive descent parsing）用相互遞迴寫起來幾乎是文法定義的直譯。

巢狀遞迴(nested recursion)：遞迴呼叫的參數本身又是一個遞迴呼叫。Ackermann 函式是經典，待會專章處理。巢狀遞迴的終止性通常難證得多，因為「內層那個參數會變多小」本身就要先遞迴地分析。

辨識遞迴的形狀很實用，因為它直接決定了該用什麼工具分析成本：線性遞迴往往是 $O(n)$；樹狀遞迴看分岔數與深度，常需記憶化挽救；相互遞迴可合併成單一遞減度量來證終止；巢狀遞迴則往往逼近不可化簡為簡單迴圈的成長率。

回溯：遞迴作為「系統化的試誤」

遞迴最有生產力的進階應用之一是回溯(backtracking)：在一棵「決策樹」上深度優先地嘗試每個選擇，走到死路就退回上一步換條路。退回這個動作，正是遞迴呼叫返回時自動發生的——你不必手動管理，呼叫堆疊替你記住了「退回後該在哪裡、狀態是什麼」。

骨架長這樣：

def backtrack(state, choices, solutions):
    if is_complete(state):           # 找到一組完整解
        solutions.append(state.copy())
        return
    for choice in choices:
        if is_valid(state, choice):  # 剪枝：不合法就不往下走
            state.append(choice)     # 做選擇
            backtrack(state, next_choices(choice), solutions)
            state.pop()              # 撤銷選擇（回溯！）
    # for 結束 = 此分支所有選擇試完，自動返回上一層

那句 state.pop() 是回溯的靈魂：在嘗試完一個選擇、子遞迴返回後，把狀態還原，才能乾淨地試下一個選擇。

看一個例子：N 皇后與剪枝的威力

在 $N \times N$ 棋盤上放 $N$ 個皇后，使其互不攻擊。逐列放置，每列嘗試每一行：

def solve_n_queens(n):
    solutions = []
    cols, diag, anti = set(), set(), set()   # 已佔用的行、兩個對角線方向

    def place(row):
        if row == n:                          # 全部 n 列都放好了
            solutions.append(1)
            return
        for col in range(n):
            if col in cols or (row - col) in diag or (row + col) in anti:
                continue                      # 剪枝：這格會被攻擊，跳過
            cols.add(col); diag.add(row - col); anti.add(row + col)
            place(row + 1)                    # 遞迴放下一列
            cols.remove(col); diag.remove(row - col); anti.remove(row + col)  # 回溯

    place(0)
    return len(solutions)

關鍵在 continue 那行的剪枝(pruning)：一旦發現某格會被既有皇后攻擊，立刻放棄整條子樹，連往下展開都不展開。沒有剪枝的暴力法要檢查 $N^N$ 種擺法；有了剪枝，搜尋樹被大幅砍掉，$N=8$ 時只需探索幾千個節點就能找出全部 92 組解。

這裡的進階體悟是：回溯的效率幾乎完全取決於剪枝。遞迴只是提供了「自動退回」的骨架，真正讓它從不可行變可行的，是你在每個節點上「能多早判斷此路不通」的洞察力。數獨、圖著色、排程、邏輯求解器，骨子裡都是同一套「遞迴 + 剪枝」。

Ackermann 函式：迴圈寫不出來的成長

入門篇說「任何遞迴都能改寫成迭代」。這句話有個重要的精確化：任何遞迴都能用「迴圈 + 顯式堆疊」模擬（前面已示範）。但若限制只用「不靠額外堆疊的單純 for/while 迴圈」（即原始遞迴, primitive recursion 能表達的範圍），那麼存在一個函式無法這樣寫——它就是 Ackermann 函式：

$$ A(m, n) = \begin{cases} n + 1 & \text{若 } m = 0 \\ A(m-1, 1) & \text{若 } m > 0,\ n = 0 \\ A(m-1,\ A(m, n-1)) & \text{若 } m > 0,\ n > 0 \end{cases} $$

def ackermann(m, n):
    if m == 0:
        return n + 1
    if n == 0:
        return ackermann(m - 1, 1)
    return ackermann(m - 1, ackermann(m, n - 1))  # 巢狀遞迴！

注意第三行是巢狀遞迴：外層呼叫的第二個參數，本身又是一個 Ackermann 呼叫。它的終止性無法只靠單一變數證明——n 有時變大（A(m, n-1) 的結果可能很大），但 m 嚴格遞減。用字典序度量 $(m, n)$ 就能證：每次遞迴要嘛 m 變小，要嘛 m 不變但 n 變小，字典序下永遠嚴格遞減，而字典序在 $\mathbb{N} \times \mathbb{N}$ 上是良基的。終止。

它的成長有多猛？$A(4, 2)$ 已是一個 $19729$ 位數的天文數字。$A(m, n)$ 對應的運算大致是：$m=1$ 加法、$m=2$ 乘法、$m=3$ 指數、$m=4$ 是「指數塔」(tetration)、$m=5$ 更是無法言喻。

Ackermann 的理論意義在於它可計算(computable)但非原始遞迴(not primitive recursive)——它證明了「能用迴圈搭配計數器表達的函式」這個類別，嚴格小於「所有可計算函式」。換句話說，遞迴（更精確地說，允許這種巢狀自我引用的 general recursion）的表達力，真的超過了單純的計次迴圈。這不是工程細節，而是可計算性理論的一塊基石。

實務上你幾乎不會去算 Ackermann 本身，但它的「反函式」$\alpha(n)$ 會在演算法分析中現身：並查集(union-find)配合路徑壓縮與按秩合併後，單次操作的攤銷複雜度是 $O(\alpha(n))$——$\alpha$ 成長極慢，對所有實際可能的 $n$ 都不超過 $4$，所以幾乎等於常數。

重點回顧

• 「有基底情形」不保證終止；真正的判準是良基遞迴：存在一個在良基集合中嚴格遞減的度量（可用 n、x+y 或字典序等）。
• 遞迴與歸納法結構對偶：基底情形對歸納基礎、遞迴情形對歸納步驟，因此可以直接用（強）歸納法證明遞迴函式正確。
• 任何遞迴都能用顯式堆疊機械化地改成迭代，把狀態從受限的系統呼叫堆疊搬到堆積區，避開深度上限。
• 遞迴有線性、樹狀、相互、巢狀等形狀；回溯是「遞迴 + 剪枝」的系統化試誤，效率取決於剪枝而非遞迴本身。
• Ackermann 函式是可計算但非原始遞迴的範例，證明 general recursion 的表達力嚴格超過單純計次迴圈。

深入探討（研究所視角）

不動點與遞迴的真正定義

我們一直把遞迴當成「函式呼叫自己」，但這在邏輯上有點循環論證的味道：定義 f 的時候用到了還沒定義完的 f，這合法嗎？指稱語意學(denotational semantics)用不動點(fixed point)給了嚴謹的答案。

把一個遞迴定義看成一個「對函式做變換的高階運算子」$F$。例如階乘對應的運算子是：「給我一個函式 $g$，我還你一個新函式：在 $0$ 回傳 $1$，否則回傳 $n \times g(n-1)$」。我們真正想要的階乘函式 fact，恰好是這個變換的不動點——滿足 $\text{fact} = F(\text{fact})$ 的那個 $g$。

# 把遞迴拆成「非遞迴的變換」F，再對它取不動點
F = lambda g: (lambda n: 1 if n == 0 else n * g(n - 1))

# Y combinator：在不靠函式名稱自我引用的情況下，造出不動點
Y = lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v)))

factorial = Y(F)
print(factorial(5))   # 120

這段程式神奇之處在於：F 完全沒有提到自己的名字，遞迴卻憑空出現了。Y 就是著名的 Y 組合子(Y combinator)，它純粹用函式（$\lambda$ 演算）就生出了自我引用的能力。Kleene 的不動點定理保證：在一個合適的偏序結構(complete partial order)上，連續運算子 $F$ 的最小不動點存在，而它正是那個「用迴圈一步步逼近、終會收斂」的遞迴函式。遞迴於是不再是「自己定義自己」的循環，而是「某個變換的最小不動點」這個堅實的數學物件。

從遞迴關係式到 Akra–Bazzi

入門篇提過主定理(Master Theorem)能解 $T(n) = a\,T(n/b) + f(n)$。但它要求所有子問題大小相同，碰到不對稱分割就失效——例如某些演算法切成 $T(n) = T(n/3) + T(2n/3) + O(n)$。這時要用更一般的 Akra–Bazzi 方法：對 $T(n) = \sum_i a_i T(n/b_i) + f(n)$，先解出滿足 $\sum_i a_i b_i^{-p} = 1$ 的指數 $p$，則

$$ T(n) = \Theta\!\left( n^p \left( 1 + \int_1^n \frac{f(u)}{u^{p+1}}\, du \right) \right). $$

對上面那個不平衡切割，$a_1=a_2=1$、$b_1=3$、$b_2=3/2$，代入解得 $p=1$，積分項給出 $\log n$ 因子，故 $T(n)=\Theta(n\log n)$——和平衡分割殊途同歸。Akra–Bazzi 讓我們能分析「分而治之但分得不均」的真實演算法（如某些選擇演算法與計算幾何演算法）。

連結到更廣的圖景

把這幾條線收攏起來：良基遞迴對應序數(ordinal)上的超限歸納，是型別論(type theory)中「結構遞迴(structural recursion)」保證程式終止的理論依據——這也是 Coq、Agda 等證明輔助器只允許「明顯遞減」遞迴的原因。不動點語意把遞迴接上 $\lambda$ 演算與可計算性。而 Ackermann 與原始遞迴的分野，則把「迴圈能算什麼」與「遞迴能算什麼」這個可計算性的核心問題說清楚。當你下次寫下一個遞迴呼叫，背後其實站著歸納法、序數、不動點與可計算性這一整座理論大廈——遞迴從來不只是一個寫程式的小技巧。