遞迴法求費波那契數列（C 語言版）

費波那契數列定義

F₀ = 0, F₁ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂ (n ≥ 2)。序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144... 注意：0 為第 0 項，非第 1 項。

遞迴實作

#include <stdio.h>
#include <stdlib.h>

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

int main() {
    int n;
    printf("請輸入要輸出多少項（自然數）費波那契數列：");
    scanf("%d", &n);

    for (int i = 0; i <= n; i++) {
        printf("%d, ", fib(i));
        if (i != 0 && i % 5 == 0) printf("\n");
    }
    printf("\n第 %d 項是：%d\n", n, fib(n));
    return 0;
}

執行範例 (n=30)

請輸入要輸出多少項（自然數）費波那契數列：30
0, 1, 1, 2, 3,
5, 8, 13, 21, 34,
55, 89, 144, 233, 377,
610, 987, 1597, 2584, 4181,
6765, 10946, 17711, 28657, 46368,
75025, 121393, 196418, 317811, 514229,
832040,
第 30 項是：832040

效能分析與改進

迭代版本範例 (O(n) 時間, O(1) 空間)

long long fib_iter(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;
}

總結

• 遞迴寫法直觀但指數級複雜，僅適合教學或極小 n。
• 實務上請使用迭代或矩陣快速冪。
• C99 long long 可存至 F₉₂ (7540113804746346429)，超過需用大整數庫。

1. 上一篇文章： C 指標原理（85）：JSON 格式介紹與 JSON-GLib 解析實戰
2. 下一篇文章： C語言實現 Huffman 樹與 Huffman 編碼：從構建到編碼的完整教學代碼

關於C

C 語言每日小練：蛇形矩陣填充算法實現

問題描述 在 n×n 方陣中按蛇形填入 1 到 n²。n=4

淺析C語言函數返回局部變量地址的「似是而非」現象

很多 C 語言初學者都會犯一個經典錯誤：在函數中返回棧上局部

Linux Socket 網路程式設計完整指南：從基礎 API 到 TCP 連接管理實戰

「一切皆 Socket」。現代網路程式幾乎全建立在 BSD

C 語言經典面試題：一年有多少秒？宏定義陷阱全解析

面試題：定義宏 SECONDS_PER_YEAR 常規答案