1.3 遞迴與迭代的轉換#

概念說明#

遞迴與迭代是同一枚硬幣的兩面。任何遞迴演算法都能改寫成迭代版（可用明確堆疊模擬呼叫），任何迭代也能寫成遞迴（把迴圈變數變成參數）。理論上兩者表達能力完全等價；實務上的取捨在於：

遞迴優點：結構貼近問題的數學定義（如樹、分治），證明容易（直接數學歸納）。
遞迴缺點：每次呼叫消耗堆疊空間，深度過大時爆棧（Python 預設上限約 1000 層）；函式呼叫有固定開銷。
迭代優點： \(O(1)\) 空間（不含資料本身）、速度快、無爆棧風險。
迭代缺點：複雜分支遞迴（如回溯、樹的遍歷）改寫後程式碼冗長、可讀性下降。

轉換的兩個標準手法：

尾遞迴消除：若遞迴呼叫是函式的最後一個動作，直接把參數改成迴圈變數即可，不需堆疊。費波那契、階乘的尾遞迴形式都是例子。可惜 CPython 不做尾呼叫最佳化，仍需手動改寫。
顯式堆疊：對非尾遞迴（如前序遍歷、河內塔），用 list 當堆疊，把「呼叫」換成「push」、「返回」換成「pop」。空間複雜度從呼叫堆疊搬到堆積，量級相同但不受遞迴深度限制。

理解轉換還有教學價值：當你把動態規劃（第 7.2 節）視為「帶備忘錄的遞迴 → 由底向上的迭代填表」，兩大流派就融會貫通了。

生活類比#

排隊換錢：遞迴像「每個櫃員把難題轉交下一位，答案再層層傳回」；迭代像「一個櫃員自己拿著紙條一步步算」。若隊伍太長（深度太大），層層轉交就會超載——這就是爆棧。

演算法步驟#

尾遞迴消除三步驟：

把遞迴呼叫的參數改成賦值語句（return f(x', y') 變成 x, y = x', y'）。
用 while True 包住函式主體。
基底情況改為 return。

顯式堆疊改寫：

建立空堆疊，push 初始任務。
迴圈：pop 一個任務，若是「計算任務」就處理；若是「待合併任務」就 push 其子任務與合併標記。

Python 範例#

import sys
sys.setrecursionlimit(10**6)

# 尾遞迴版階乘
def fact_rec(n, acc=1):
    if n <= 1:
        return acc
    return fact_rec(n - 1, acc * n)

# 消除尾遞迴 → 迭代
def fact_iter(n):
    acc = 1
    while n > 1:
        acc *= n
        n -= 1
    return acc

# 非尾遞迴 → 顯式堆疊：樹的前序遍歷
def preorder(tree):
    out, stack = [], [tree]
    while stack:
        node = stack.pop()
        if node is None:
            continue
        val, left, right = node
        out.append(val)          # 先訪根
        stack.append(right)      # 右先壓，左先出
        stack.append(left)
    return out

t = (1, (2, None, None), (3, None, (4, None, None)))
print(fact_rec(10) == fact_iter(10))  # True
print(preorder(t))                    # [1, 2, 3, 4]

複雜度與收斂性分析#

尾遞迴消除後：時間不變、空間由 \(O(n)\) （堆疊）降為 \(O(1)\) 。顯式堆疊版時間空間量級與遞迴相同（皆 \(O(n)\) 節點、 \(O(h)\) 堆疊），但避開了 Python 的遞迴深度限制與呼叫開銷。實測上迭代版通常快 1.5 至 3 倍。選擇準則：深度可控且問題天然分治，用遞迴；深度可能很大或追求效能，用迭代。

練習#

將河內塔遞迴解改寫為顯式堆疊版本，並驗證 \(n=3\) 時移動序列相同。
費波那契遞迴版時間複雜度是 \(O(\varphi^n)\) ，迭代版 \(O(n)\) 。解釋差距來源（提示：子問題重複計算），這正是 7.2 節動態規劃的伏筆。
寫一個迭代版的 Ackermann 函數 \(A(2, 3)\) ，體會「遞迴不等於簡單」。