C語言遞歸與迭代實現斐波那契數列：第 n 項與前 n 項和

斐波那契數列 C 語言實現：遞歸、迭代、動態規劃三種算法對比

斐波那契數列定義：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n≥2)。本文實現：輸入 n，輸出第 n 項值與前 n 項和。重點分析遞歸效率陷阱與優化方案。

1. 朴素遞歸（教學演示，極其低效）

#include <stdio.h>

int fib_rec(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib_rec(n-1) + fib_rec(n-2); // 指數級重複計算
}

int sum_rec(int n) { // 同樣低效
    if (n <= 0) return 0;
    return fib_rec(n) + sum_rec(n-1);
}

int main() {
    int n;
    printf("輸入 n (建議 < 40): "); scanf("%d", &n);
    printf("F(%d) = %d\n", n, fib_rec(n));
    printf("前 %d 項和 = %d\n", n, sum_rec(n));
    return 0;
}

缺點：時間複雜度 O(2ⁿ)，n=40 明顯卡頓，n=50 可能跑幾分鐘。僅供理解遞歸定義，生產環境禁用。

2. 迭代法（O(n) 時間，O(1) 空間，工程首選）

#include <stdio.h>

void fib_iter(int n, long long *fn, long long *sum) {
    long long a = 0, b = 1, s = 0;
    if (n == 0) { *fn = 0; *sum = 0; return; }
    if (n == 1) { *fn = 1; *sum = 1; return; }
    s = 1; // F(0)+F(1)
    for (int i = 2; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
        s += c;
    }
    *fn = b;
    *sum = s;
}

int main() {
    int n;
    long long fn, sum;
    printf("輸入 n: "); scanf("%d", &n);
    fib_iter(n, &fn, &sum);
    printf("F(%d) = %lld\n", n, fn);
    printf("前 %d 項和 = %lld\n", n, sum);
    return 0;
}

使用 long long 延緩溢出（n=92 時 F(n) 超過 64 位）。需更大數可用 unsigned long long 或大整數庫。

3. 動態規劃 / 記憶化遞歸（O(n) 時間，O(n) 空間）

#include <stdio.h>
#define MAX_N 1000

long long memo[MAX_N];
int vis[MAX_N];

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

int main() {
    int n;
    printf("輸入 n: "); scanf("%d", &n);
    long long fn = fib_memo(n);
    long long sum = 0;
    for (int i = 0; i <= n; i++) sum += fib_memo(i);
    printf("F(%d) = %lld,  sum = %lld\n", n, fn, sum);
    return 0;
}

4. 矩陣快速冪 / 通項公式（O(log n) 進階）

利用矩陣 [[1,1],[1,0]]^n 或 Binet 公式可在對數時間求值，屬於算法競賽進階技巧，此處不展開。

主函數返回類型修正

C 標準要求 int main() 或 int main(void)，並以 return 0; 結束。void main() 為舊式非標準寫法，現代編譯器會警告。

算法複雜度總結

總結

斐波那契數列是遞歸與動態規劃的經典入門題。實際編程中請務必使用迭代法，避免指數級爆炸。理解遞歸定義與迭代實現的等價轉換，是演算法思維訓練的核心一課。