遞迴求費波那契數列 C 語言實現與效能分析

數學定義

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)  (n ≥ 2)

數列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

注意：第 0 項為 0，非第 1 項。

遞迴實現

#include 

int fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n-1) + fib_recursive(n-2);
}

int main() {
    int n;
    printf("請輸入項數 (0-based)：");
    scanf("%d", &n);
    for (int i = 0; i <= n; ++i) {
        printf("%d ", fib_recursive(i));
        if (i % 5 == 0) printf("\n");
    }
    printf("\nF(%d) = %d\n", n, fib_recursive(n));
    return 0;
}

執行結果範例 (n=10)

0 1 1 2 3
5 8 13 21 34
55
F(10) = 55

效能災難分析

• 時間複雜度：O(2^n) 指數級增長。fib(40) 需約 10 億次遞迴呼叫。
• 重複計算：`fib(5)` 呼叫 `fib(4)` 和 `fib(3)`，`fib(4)` 又呼叫 `fib(3)` 和 `fib(2)`... 子問題極度重疊。
• 堆疊溢位：深度 n，大 n 導致堆疊耗盡。

優化方案對比

推薦：迭代實現 (O(n) 時間, O(1) 空間)

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

備忘錄遞迴 (教學用)

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

大數字處理

F(93) 超過 64 位有號整數範圍。需用大整數庫 (GMP) 或自陣列實現高精度加法。