遞迴教學：運作原理與 Python 範例

遞迴解決什麼問題

有些問題本身就是用自己來定義的。資料夾裡有檔案，也有其他資料夾；樹的節點底下有子樹；n 的階乘是 n 乘以 n − 1 的階乘。若只用一般迴圈來寫，往往得自己維護一個存放待處理工作的堆疊；遞迴則讓語言替你保管這個堆疊。

遞迴函式有兩個部分：

• 基本情況：最小的輸入，直接給出答案。以階乘為例，0! = 1。
• 遞迴情況：縮小問題，對較小的部分呼叫函式，再把結果合併。以階乘為例，n! = n × (n − 1)!。

def factorial(n):
    if n == 0:                  # base case
        return 1
    return n * factorial(n - 1) # recursive case
print(factorial(5))   # 120

呼叫堆疊逐步追蹤

每次呼叫都會在呼叫堆疊上取得自己的堆疊框（frame），裡面存著自己那份 n。呼叫一路往下到基本情況，然後結果再依相反順序一路返回。

這裡的堆疊深度是 n + 1 個堆疊框，所以即使沒有建立任何串列，額外空間仍是 O(n)。

對巢狀資料做遞迴

當資料的形狀本身就是遞迴結構時，遞迴最好用。下面這個函式會加總一個串列中所有的數字，而這個串列裡可能再包含其他串列，深度不限。

def deep_sum(items):
    total = 0
    for x in items:
        if isinstance(x, list):
            total += deep_sum(x)   # same problem, smaller piece
        else:
            total += x
    return total
print(deep_sum([1, [2, 3], [4, [5, [6]]]]))   # 21

同樣的模式也能走訪目錄樹、JSON 文件、HTML DOM 或二元樹：處理目前的節點，再對每個子節點遞迴。

def power_set(items):
    if not items:
        return [[]]
    rest = power_set(items[1:])
    return rest + [[items[0]] + s for s in rest]
print(power_set([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

遞迴函式的複雜度

成本的估算方式是（呼叫次數）×（每次呼叫的工作量）。空間至少等於最大的堆疊深度。

分而治之的遞迴式，例如合併排序的 T(n) = 2T(n/2) + O(n)，解出來是 O(n log n)。若函式對 n − 1 呼叫兩次，則成長是指數級的。

記憶化：不要重複做同樣的事

單純遞迴的費氏數列函式會把相同的值重複算很多次：fib(5) 會呼叫 fib(3) 兩次、fib(2) 三次。每個結果在第一次算出時就快取起來，就能把指數時間變成線性時間。Python 的 functools.lru_cache（或 Python 3.9 以上的 functools.cache）只要一個裝飾器就能辦到。

from functools import lru_cache
def fib_slow(n):
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
print(fib_slow(20))   # 6765, about 22,000 calls
print(fib(90))        # 2880067194370816120, 91 distinct calls

記憶化遞迴是動態規劃的由上而下形式；由下而上的形式則是用迴圈來填表。

遞迴限制與改寫成迴圈

你可以用 sys.setrecursionlimit() 調高上限，但太深的遞迴仍可能讓直譯器當機。如果輸入可能很深，例如一百萬個節點的鏈結串列或退化的樹，請改用迴圈搭配明確的堆疊來改寫。

def deep_sum_iter(items):
    total, stack = 0, [items]
    while stack:
        current = stack.pop()
        for x in current:
            if isinstance(x, list):
                stack.append(x)
            else:
                total += x
    return total
print(deep_sum_iter([1, [2, 3], [4, [5, [6]]]]))   # 21

常見錯誤

• 漏掉基本情況，或基本情況永遠到不了。例如用上面的程式碼執行 factorial(-1)，永遠不會到 0，最後以 RecursionError 結束。
• 遞迴情況沒有縮小輸入，例如在 f(n) 裡又呼叫 f(n)。
• 忘了 return 遞迴的結果：factorial(n - 1) 前面沒有 return，會得到 None。
• 每次呼叫都複製資料。items[1:] 會複製串列，所以對長串列的切片做遞迴，時間成本是 O(n²)；請改傳索引。
• 用可變的預設參數，例如 def f(x, seen=[]) 來在多次呼叫之間傳遞狀態；函式的每一次呼叫都會共用同一個串列。

何時該用遞迴

當資料或問題本身就是遞迴結構時，就適合用遞迴：樹、圖（深度優先搜尋）、巢狀結構、運算式剖析、回溯法（排列、N 皇后、數獨），以及分而治之（合併排序、快速排序、二分搜尋）。如果問題只是單純的序列，或在 Python 中深度會隨輸入規模增長，就用迴圈。

面試時，遞迴題常用來檢查你能否說明基本情況、遞迴情況、包含堆疊在內的時間與空間成本，以及記憶化何時有幫助。