Python 預設不支援尾遞歸優化 (TCO)，遞歸深度超過 1000 即拋出 RecursionError。本文介紹利用裝飾器 + 異常機制模擬 TCO，實現階乘與費波納契數列的深度遞歸計算而不爆棧。

尾遞歸定義與優化原理

• 尾遞歸：遞歸調用為函式最後一步操作，且返回值不參與運算
• 優化原理：編譯器覆蓋當前棧幀而非新建，棧空間 O(1)
• Python 現狀：Guido 明確拒絕支援 TCO，需自行實現

裝飾器實作：異常劫持棧幀

import sys

class TailRecurseException(Exception):
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs

def tail_call_optimized(g):
    """裝飾器：檢測尾遞歸並拋出異常模擬跳轉"""
    def func(*args, **kwargs):
        f = sys._getframe()
        # 檢查是否為自己的「祖父」幀（即尾遞歸調用）
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while True:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException as e:
                    args = e.args
                    kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func

應用範例：階乘與費波納契

@tail_call_optimized
def factorial(n, acc=1):
    "calculate a factorial"
    if n == 0:
        return acc
    return factorial(n-1, n*acc)

print(factorial(10000))  # 不會觸發 RecursionError

@tail_call_optimized
def fib(i, current=0, next=1):
    if i == 0:
        return current
    else:
        return fib(i - 1, next, current + next)

print(fib(10000))  # 同理安全執行

關鍵機制解析

1. 幀檢查：f.f_back.f_back.f_code == f.f_code 判斷是否為尾遞歸（隔一層調用者為自己）
2. 異常傳遞參數：TailRecurseException 攜帶新參數「跳回」外層 while 迴圈
3. 迴圈替代遞歸：外層 while True 不斷捕獲異常並重新調用，實現棧幀複用

限制與注意事項

• 僅對直接尾遞歸有效，間接遞歸（A→B→A）不支援
• 依賴 sys._getframe() 內部 API，CPython 專屬，PyPy/Jython 不保證
• 除錯困難：堆疊追蹤被異常機制改寫
• 效能：異常拋捕開銷大，極深遞歸較迴圈慢

現代替代方案

方案	適用場景
改寫為迴圈	所有尾遞歸可機械轉換，效能最佳
functools.lru_cache + 遞歸	重疊子問題（如費波納契），記憶化避免重複計算
sys.setrecursionlimit()	輕微加深限制（慎用，可能導致段錯誤）
asyncio/生成器	非阻塞協程模式替代遞歸

總結

尾遞歸優化裝飾器是理解 Python 執行模型、異常控制流、幀物件操作的優秀教學案例，但生產代碼強烈建議改寫為迴圈。理解其原理有助於識別何時可安全遞歸、何時必須迴圈。