C 語言遞歸經典：斐波那契數列模擬兔子繁殖問題（含遞歸效率陷阱）

問題描述

經典兔子繁殖問題：一對兔子，出生後第 3 個月起每月產一對，新生兔子長到第 3 個月也開始產仔，假設不死。求第 n 月兔子總對數。這正是斐波那契數列：F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)。

原代碼：遞歸實現（指數級爆炸）

#include <stdio.h>

int f(int n);  // 遞歸函數

int main() {
    int month, i, sum = 0;
    printf("請輸入月數: ");
    scanf("%d", &month);
    for (i = 1; i <= month; i++) {
        sum += f(i);  // ❌ 累加每月「新出生對數」？題目問「總數」
    }
    printf("第 %d 月，兔子總數 %d 對\n", month, sum);
    return 0;
}

int f(int n) {
    if (n == 1 || n == 2) return 1;
    return f(n-2) + f(n-1);  // 標準遞歸
}

關鍵問題分析

1. 邏輯誤解：f(n) 是「第 n 月總對數」而非「新出生對數」

• 遞歸 f(n) 直接給出第 n 月總對數（斐波那契定義）。
• 原代碼 sum += f(i) 將每月總數累加，結果完全錯誤。正確應直接輸出 f(month)。

2. 遞歸效率災難：時間複雜度 O(2ⁿ)

f(5) = f(4) + f(3)
     = f(3)+f(2) + f(2)+f(1)
     = f(2)+f(1)+1 + 1+1 ...
大量重複計算：f(3) 算 2 次，f(2) 算 3 次...
調用次數 ≈ 1.618ⁿ (黃金比例指數增長)

n=40 時需約 1.6 億次調用，明顯卡頓；n=50 約 200 億次，不可接受。

優化方案對比

迭代 DP 標準實現 (生產首選)

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

遞歸 + 備忘錄 (教學展示 DP 思想)

#define MAX_N 100
long long memo[MAX_N] = {0};

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

矩陣快速冪 (大 n 高性能)

typedef struct { long long a, b, c, d; } Matrix;

Matrix mul(Matrix x, Matrix y) {
    return (Matrix){
        x.a*y.a + x.b*y.c,  x.a*y.b + x.b*y.d,
        x.c*y.a + x.d*y.c,  x.c*y.b + x.d*y.d
    };
}

Matrix mpow(Matrix base, int exp) {
    Matrix res = {1,0,0,1};  // 單位矩陣
    while (exp) {
        if (exp & 1) res = mul(res, base);
        base = mul(base, base);
        exp >>= 1;
    }
    return res;
}

long long fib_matrix(int n) {
    if (n <= 2) return 1;
    Matrix M = {1,1,1,0};  // 斐波那契矩陣
    Matrix R = mpow(M, n-2);
    return R.a + R.b;  // F(n) = R.a*F(2) + R.b*F(1)
}

溢出邊界：長整型極限

n>93 需大整數庫或高精度模擬。

正確主程序

int main() {
    int month;
    printf("請輸入月數 (1-92): ");
    if (scanf("%d", &month) != 1 || month < 1) return 1;

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

總結

兔子繁殖問題是斐波那契數列的經典建模來源。原代碼暴露了遞歸理解偏差（累加總數）與指數級遞歸效率陷阱。關鍵收穫：

• 斐波那契定義：F(n) = F(n-1) + F(n-2)，直接給出第 n 項值，無需累加；
• 裸遞歸 O(2ⁿ) 只適合教學演示 n≤30，生產禁用；
• 迭代 DP O(n)/O(1) 為工程標準解；
• 矩陣快速冪 O(log n) 解決大 n 高性能需求；
• long long 支持到 n=92，超過需大整數。