您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言遞迴實作費波那契數列：經典兔子繁殖問題與遞迴效率陷阱

編輯：關於C

問題背景

費波那契數列：F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)。
對應「兔子繁殖」：第 n 月兔子對數 = 第 n-1 月總數 + 新出生對數（等於 n-2 月總數）。

遞迴版程式碼（教學用）

#include <stdio.h>

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

int main()
{
    int month;
    printf("請輸入月數: ");
    scanf("%d", &month);

    long long total = 0;
    for (int i = 1; i <= month; i++)
        total += fib(i);

    printf("第 %d 月兔子總數: %lld\n", month, total);
    return 0;
}

⚠️ 遞迴效率災難

fib(n) 時間複雜度 O(2^n)，重複計算極多：

fib(5) = fib(4) + fib(3)
       = fib(3)+fib(2) + fib(2)+fib(1)
       = fib(2)+fib(1)+1 + 1+1 ...

fib(40) 需 ~10 億次呼叫，明顯卡頓；fib(50) 可能跑數分鐘。

三種優化方案

方法	時間複雜度	空間複雜度	程式碼長度
遞迴 + 備忘錄	O(n)	O(n)	+陣列
迭代（雙變數）	O(n)	O(1)	短
矩陣快速冪	O(log n)	O(1)	較長

迭代版（推薦實務用）


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