遞迴（Recursion）#

遞迴是一種函式自己呼叫自己的程式設計技巧。從演算法思想來看，遞迴是一種特殊的迴圈，透過函式呼叫的堆疊（Stack）來實現重複執行。

遞迴的本質#

去的過程叫「遞」，回來的過程叫「歸」。遞迴將問題分解為更小規模的子問題，直到達到終止條件，再將結果層層返回。

經典比喻：電影院找座位#

你在電影院想知道自己在第幾排，但太暗看不清。於是你問前面的人，前面的人也問他前面的人，直到第一排的人說「我在第一排」，答案再一層層傳回來。

f(n) = f(n-1) + 1，其中 f(1) = 1

遞迴三條件#

只要同時滿足以下三個條件，就可以用遞迴來解決：

1. 問題可分解為子問題 - 子問題是資料規模更小的同類問題
2. 求解思路完全相同 - 問題與子問題除了資料規模不同，處理方式一樣
3. 存在終止條件 - 必須有停止遞迴的邊界條件

遞迴程式碼模板#

flowchart TD
    A[進入遞迴] --> B{1. 終止條件<br/>level > MAX?}
    B -->|是| C[處理結果並返回]
    B -->|否| D[2. 處理當前層邏輯]
    D --> E[3. 下探到下一層<br/>recursion level+1]
    E --> F[4. 清理當前層狀態<br/>回溯恢復]
    F --> G[返回上一層]

    style B fill:#fff3e0
    style C fill:#e8f5e9
    style E fill:#e3f2fd
    style F fill:#fce4ec

def recursion(level, param1, param2, ...):
    # 1. Recursion Terminator (終止條件) - 最優先編寫
    if level > MAX_LEVEL:
        process_result()
        return

    # 2. Process Logic (處理當前層邏輯)
    process(level, data...)

    # 3. Drill Down (下探到下一層)
    recursion(level + 1, p1, ...)

    # 4. Reverse State (清理當前層狀態，如需要)
    # 例如：恢復全域變數、回溯法中的路徑重置

寫遞迴程式碼的關鍵：寫出遞推公式，找到終止條件。不要試圖用人腦展開每一層遞迴，只需思考當前層與下一層的關係。

經典案例：爬樓梯#

假設有 n 個台階，每次可以跨 1 或 2 個台階，問有多少種走法？

遞推公式：

f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2)

def climb_stairs(n):
    if n == 1: return 1
    if n == 2: return 2
    return climb_stairs(n-1) + climb_stairs(n-2)

遞迴的常見問題#

1. 堆疊溢出（Stack Overflow）#

函式呼叫會使用栈來保存臨時變數，遞迴深度過深會導致堆疊溢出。

解決方案：限制遞迴深度

depth = 0
def f(n):
    global depth
    depth += 1
    if depth > 1000:
        raise Exception("遞迴深度超限")
    # ...

2. 重複計算#

以費氏數列為例，計算 f(6) 時，f(4) 會被計算多次。

含有大量重複子問題的樸素遞迴，時間複雜度往往是指數級 O(2^n)。

解決方案：記憶化（Memoization）

memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

3. 其他問題#

• 時間效率：函式呼叫本身有開銷
• 空間複雜度：遞迴呼叫需要保存現場資料，空間複雜度為 O(n)

遞迴轉迭代#

所有遞迴理論上都可以改寫為迭代（迴圈），但在樹、圖的走訪中，遞迴提供了更好的可讀性。

def climb_stairs_iterative(n):
    if n == 1: return 1
    if n == 2: return 2

    prepre, pre = 1, 2
    for i in range(3, n + 1):
        current = pre + prepre
        prepre = pre
        pre = current
    return pre

實戰技巧#

不要人肉遞迴！ 初學者常嘗試在腦中模擬每一層的執行，這很容易「爆腦」。應關注當前層的邏輯以及與下一層的介面，相信子問題已經被正確解決。