遞迴與尾遞迴深度解析：從斐波那契看效能優化

遞迴與尾遞迴深度解析

遞迴是函數直接或間接呼叫自身的程式設計技巧。雖然代碼簡潔，但傳統遞迴存在堆疊溢出與重複計算問題。尾遞迴透過編譯器優化可轉為迭代，本文以斐波那契數列為例深度對比三種實作。

1. 一般遞迴：指數級複雜度

int Fib(int n) {
    if (n < 2) return n;
    return Fib(n-1) + Fib(n-2);  // 兩個遞迴呼叫
}

執行樹狀結構 (n=5)：

          Fib(5)
         /      \
     Fib(4)    Fib(3)
    /    \     /    \
 Fib(3) Fib(2) Fib(2) Fib(1)
  ...

缺點：

• 時間複雜度 O(2^n)，大量重複計算（紅色節點）
• 空間複雜度 O(n) 堆疊深度，n=50 即可能堆疊溢出

2. 尾遞迴：線性複雜度 + 常數空間（經優化）

尾遞迴定義：遞迴呼叫是函數的最後一個動作，且其返回值直接作為函數返回值，無後續運算。

int Fib_Tail(int n, int a, int b) {
    if (n == 0) return a;                    // 基礎情況
    return Fib_Tail(n - 1, b, a + b);        // 尾呼叫，無額外運算
}

// 呼叫入口
int Fib(int n) { return Fib_Tail(n, 0, 1); }

執行軌跡 (n=5)：

Fib_Tail(5, 0, 1)
→ Fib_Tail(4, 1, 1)
→ Fib_Tail(3, 1, 2)
→ Fib_Tail(2, 2, 3)
→ Fib_Tail(1, 3, 5)
→ Fib_Tail(0, 5, 8) → return 5

參數 a 保存當前結果，b 保存下一結果。每次遞迴只更新參數，無額外堆疊框架需求（經編譯器優化後）。

3. 迭代法：最佳實務選擇

int Fib_Iter(int n) {
    if (n < 2) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

邏輯與尾遞迴同構，但無函數呼叫開銷，編譯器最易優化，除錯最直觀。

效能對比總結

* 依賴編譯器支援尾呼叫優化 (TCO)。GCC/Clang -O2 預設開啟，MSVC 需特定條件。

編譯器優化驗證

$ gcc -O2 -S fib.c -o fib.s
# 查看組合語言，尾遞迴版應無 call 指令，僅有 jmp/迴圈

何時使用哪種？

• 教學/原型驗證：一般遞迴最直觀
• 函數式語言/要求遞迴表達：尾遞迴 + 確認 TCO
• 生產環境 C/C++：優先選擇迭代，確定性能能、無驚喜
• 樹/圖遍歷：顯式堆疊模擬遞迴，避免堆疊溢出

進階：記憶化遞迴

若必須用遞迴結構，加入快取避免重複計算：

int memo[100] = {0};
int Fib_Memo(int n) {
    if (n < 2) return n;
    if (memo[n]) return memo[n];
    return memo[n] = Fib_Memo(n-1) + Fib_Memo(n-2);  // O(n) 時間
}