Python 遞迴 (Recursion)

遞迴是指函數呼叫自己本身的程式設計技巧。遞迴可以將複雜的問題分解成較小的相同問題來解決。

基本概念

一個遞迴函數必須包含：

1. 基本情況 (Base Case)：停止遞迴的條件，避免無窮遞迴
2. 遞迴情況 (Recursive Case)：函數呼叫自己，但問題規模變小

def countdown(n):
    # 基本情況
    if n <= 0:
        print("Done!")
        return
    
    # 遞迴情況
    print(n)
    countdown(n - 1)

countdown(5)

輸出：

5
4
3
2
1
Done!

經典範例

階乘 (Factorial)

n! = n × (n-1) × (n-2) × ... × 1

def factorial(n):
    # 基本情況
    if n == 0 or n == 1:
        return 1
    
    # 遞迴情況
    return n * factorial(n - 1)

print(factorial(5))  # 120 (5 × 4 × 3 × 2 × 1)
print(factorial(0))  # 1

執行過程：

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

費氏數列 (Fibonacci)

F(n) = F(n-1) + F(n-2)，其中 F(0) = 0, F(1) = 1

def fibonacci(n):
    # 基本情況
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # 遞迴情況
    return fibonacci(n - 1) + fibonacci(n - 2)

# 印出前 10 個費氏數
for i in range(10):
    print(fibonacci(i), end=" ")
# 0 1 1 2 3 5 8 13 21 34

最大公因數 (GCD)

使用輾轉相除法：

def gcd(a, b):
    # 基本情況
    if b == 0:
        return a
    
    # 遞迴情況
    return gcd(b, a % b)

print(gcd(48, 18))  # 6
print(gcd(100, 25)) # 25

次方計算

def power(base, exp):
    # 基本情況
    if exp == 0:
        return 1
    
    # 遞迴情況
    return base * power(base, exp - 1)

print(power(2, 10))  # 1024
print(power(3, 4))   # 81

處理資料結構

加總巢狀 List

def nested_sum(lst):
    total = 0
    for item in lst:
        if isinstance(item, list):
            total += nested_sum(item)  # 遞迴處理巢狀 list
        else:
            total += item
    return total

data = [1, [2, 3], [4, [5, 6]], 7]
print(nested_sum(data))  # 28

扁平化巢狀 List

def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

data = [1, [2, 3], [4, [5, 6]], 7]
print(flatten(data))  # [1, 2, 3, 4, 5, 6, 7]

遍歷目錄結構

import os

def list_files(path, indent=0):
    for item in os.listdir(path):
        full_path = os.path.join(path, item)
        print("  " * indent + item)
        if os.path.isdir(full_path):
            list_files(full_path, indent + 1)

# list_files("/path/to/directory")

遞迴的優化

記憶化 (Memoization)

儲存已計算的結果，避免重複計算：

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(100))  # 很快就能算出來

使用 functools.lru_cache 裝飾器更簡潔：

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(100))

尾遞迴 (Tail Recursion)

尾遞迴是指遞迴呼叫是函數的最後一個操作：

# 一般遞迴
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)  # 還要乘以 n

# 尾遞迴
def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, n * acc)  # 直接回傳遞迴結果

print(factorial_tail(5))  # 120

遞迴深度限制

Python 預設的遞迴深度限制是 1000，超過會發生 RecursionError：

import sys

# 查看目前的限制
print(sys.getrecursionlimit())  # 1000

# 修改限制（謹慎使用）
sys.setrecursionlimit(2000)

遞迴 vs 迴圈

很多遞迴問題都可以用迴圈解決：

# 遞迴版本
def factorial_recursive(n):
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)

# 迴圈版本
def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

何時使用遞迴：

• 問題本身具有遞迴結構（如樹、圖）
• 程式碼更簡潔易讀
• 遞迴深度不會太深

何時使用迴圈：

• 效能要求高
• 遞迴深度可能很深
• 問題容易用迴圈表達