C語言實現斐波那契數列：遞歸與迭代算法解析

斐波那契數列 C 語言實現指南

斐波那契數列是經典的程式設計練習題，定義為：F(1)=1, F(2=1, F(n)=F(n-1)+F(n-2) (n>2)。本文提供遞歸與迭代兩種實現方式，並分析效能差異。

遞歸實現（教學示範）

#include <stdio.h>

long fibonacci_recursive(int n) {
    if (n == 1 || n == 2) return 1;
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}

int main() {
    int n;
    printf("請輸入月份（項數）：");
    scanf("%d", &n);
    if (n < 1) {
        printf("輸入無效\n");
        return 1;
    }
    printf("第 %d 項為：%ld\n", n, fibonacci_recursive(n));
    return 0;
}

缺點：時間複雜度 O(2^n)，重複計算極多，n > 40 時明顯卡頓。

迭代實現（生產環境推薦）

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

優點：時間複雜度 O(n)，空間複雜度 O(1)，可計算極大項數（配合 unsigned long long 或大整數庫）。

進階：矩陣快速冪 / 通項公式

對於極大 n（如 10^9），可使用矩陣快速冪將複雜度降至 O(log n)，或使用 Binet 公式（需高精度浮點）。

總結

• 理解遞歸邏輯：適合教學、小規模 n。
• 實際開發用迭代：高效、穩定、無棧溢出風險。
• 注意整數溢出：long 通常 4/8 字節，第 47 項即超過 32 位有號整數範圍，建議用 unsigned long long 或任意精度庫。