C語言遞歸實作費波納契數列：經典與效能的權衡

遞歸實作費波納契數列雖然程式碼極度簡潔，完美對應數學定義，但其指數級時間複雜度使其在實務應用中極受限制。本文深入剖析遞歸解法的運作機制、效能瓶頸與改良方向。

遞歸程式碼結構

#include <stdio.h>

int fibonacci(int num);

int main() {
    int num, result;
    printf("請輸入項數: ");
    scanf("%d", &num);
    result = fibonacci(num);
    printf("第 %d 項結果: %d\n", num, result);
    return 0;
}

int fibonacci(int num) {
    if (num == 1 || num == 2)
        return 1;
    return fibonacci(num - 1) + fibonacci(num - 2);
}

遞歸執行流程圖解

以 fibonacci(5) 為例，呼叫樹呈現二元樹結構：

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) → 1
│   │   └── fib(1) → 1
│   └── fib(2) → 1
└── fib(3)
    ├── fib(2) → 1
    └── fib(1) → 1

總共產生 9 次函數呼叫，其中 fib(3)、fib(2)、fib(1) 重複計算多次。

效能致命傷：指數級複雜度

• 時間複雜度：O(2^n)，n=40 時需超過 10 億次呼叫
• 空間複雜度：O(n) 堆疊深度，n 過大導致堆疊溢位
• 重複計算：大量子問題被重複求解，無記憶化機制

記憶化遞歸優化

引入陣列快取已計算結果，將時間複雜度降至 O(n)：

#include <stdio.h>
#define MAX 100

long long memo[MAX];

long long fib_memo(int n) {
    if (n <= 2) return 1;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib_memo(n-1) + fib_memo(n-2);
}

遞歸與迭代綜合比較

實務建議

1. 教學階段：使用遞歸理解數學定義與遞歸思維
2. 工程應用：採用迭代或矩陣快速冪，必要時配合大數處理
3. 遞歸改寫：尾遞歸優化、記憶化、動態規劃底-up 方式

遞歸版費波納契是理解遞歸機制的優良教材，但生產環境務必避免直接使用朴素遞歸。掌握從遞歸到迭代、記憶化、動態規劃的演進路徑，是演算法優化的核心能力之一。