遞迴（Recursion）是程式設計中函式直接或間接呼叫自身的程式結構，透過分解問題為相似子問題並逐步簡化至基礎情況來解決複雜任務。它需要明確的**終止條件（Base Case）**避免無限循環，利用函式呼叫堆疊（Call Stack）自動管理狀態，是分治演算法、樹狀遍歷與動態規劃的基礎概念。
遞迴的核心組成：兩個必要元素
每個遞迴函式必須包含：
-
基礎情況（Base Case）：停止遞迴的條件，直接返回結果
-
遞迴情況（Recursive Case）：呼叫自身，問題規模縮小
經典階乘範例：
def factorial(n):
# 基礎情況
if n <= 1:
return 1
# 遞迴情況：n! = n × (n-1)!
return n * factorial(n - 1)
print(factorial(5)) # 5 × 4 × 3 × 2 × 1 = 120
執行過程（呼叫堆疊）：
factorial(5) → 5 × factorial(4)
→ 5 × 4 × factorial(3)
→ 5 × 4 × 3 × factorial(2)
→ 5 × 4 × 3 × 2 × factorial(1)
→ 5 × 4 × 3 × 2 × 1 = 120 ✓
遞迴的運作原理：呼叫堆疊
遞迴依賴**後進先出（LIFO）**的函式堆疊：
-
每次遞迴呼叫產生新堆疊框架，儲存局部變數與返回位址
-
抵達基礎情況時，返回值逐層回傳
-
堆疊框架依序銷毀，重建完整結果
堆疊成長：factorial(5) ← factorial(4) ← factorial(3)
堆疊縮減：factorial(3) → 6 → factorial(2) → 2 → factorial(1) → 1
最終：120
經典遞迴問題範例
1. 斐波那契數列
fib(n) = fib(n-1) + fib(n-2), fib(0)=0, fib(1)=1
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
2. 河內塔（Hanoi Tower）
移動 n 個圓盤的步驟：
1. 移動 n-1 個圓盤到輔助柱
2. 移動第 n 個圓盤到目標柱
3. 移動 n-1 個圓盤到目標柱
def hanoi(n, source, target, auxiliary):
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
hanoi(n-1, source, auxiliary, target)
print(f"Move disk {n} from {source} to {target}")
hanoi(n-1, auxiliary, target, source)
遞迴 vs 迭代：效能與適用性
| 特性 | 遞迴 | 迭代 |
|---|---|---|
| 可讀性 | 高（數學直觀） | 中 |
| 記憶體 | O(n) 堆疊空間 | O(1) |
| 效能 | 慢（重複計算） | 快 |
| 除錯 | 難（堆疊追蹤） | 易 |
| 適用 | 樹、圖、分治 | 線性問題 |
斐波那契效能對比：
遞迴：fib(40) ≈ 102,334,155 次呼叫，超時
迭代：O(n) 時間，0.001 秒完成
尾遞迴優化（Tail Recursion）
尾遞迴將遞迴呼叫置於函式末尾，編譯器可優化為迭代：
# 普通遞迴（堆疊成長）
def factorial(n, accumulator=1):
if n <= 1:
return accumulator
return factorial(n-1, n * accumulator) # 尾遞迴
# 某些語言（如 Scheme）自動優化為 O(1) 空間
遞迴的實際應用場景
1. 樹狀結構遍歷
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder(node):
if not node: # 基礎情況
return
print(node.val) # 前序：根→左→右
preorder(node.left)
preorder(node.right)
2. 分治演算法
-
快速排序：選樞紐，分治排序左右子陣列
-
合併排序：分割陣列，遞迴排序後合併
-
二元搜尋：遞迴搜尋半邊區間
3. 組合問題
-
全排列：固定一位，遞迴排列其餘
-
N 皇后問題：試探法 + 遞迴回溯
遞迴除錯技巧
1. 手動模擬小輸入：factorial(3)、fib(4)
2. 印製呼叫參數：print(f"factorial({n})")
3. 畫出遞迴樹：視覺化呼叫關係
4. 檢查基礎情況：是否涵蓋所有終止分支
5. 驗證問題縮小：參數是否確實變小
常見陷阱與解決方案
無限遞迴：
def bad_recursive(n): # 缺少基礎情況
return bad_recursive(n) # Stack Overflow!
錯誤基礎情況：
def factorial(n):
if n == 0: # 漏掉 n=1
return 1
return n * factorial(n-1) # n=1 無限遞迴
最佳實務：
def safe_factorial(n):
if n < 0:
raise ValueError("輸入必須是非負整數")
if n <= 1:
return 1
return n * safe_factorial(n-1)
遞迴思維訓練
解題三步法：
-
找到遞迴關係：
問題(n) = 簡單步驟 + 問題(n-1) -
定義基礎情況：
問題(0/1) = 已知答案 -
驗證縮小性：
問題規模是否確實減小？
遞迴改變程式思考方式，從「怎麼重複」轉為「問題如何分解」。雖然迭代通常更快，但遞迴在樹狀問題、分治演算法與數學證明中無可取代，是掌握進階演算法的入場券。練習經典題目如全排列、N 皇后，就能內化這種強大思維模式。