經典遞迴題目：兔子繁殖問題（費波那契數列）的 C 語言實作與數學解析

編輯：關於C語言

「有一對兔子，從出生後第 3 個月起每個月生一對兔子，小兔子長到第 3 個月後每個月又生一對兔子，假設兔子不死，求每個月兔子總數。」這是費波那契數列最著名的應用場景。本文從數學建模、遞迴關係、迭代實作、矩陣快速冪、封閉式公式（Binet 公式）五個維度完整解析，並提供生產級 C 程式碼。

數學建模

設 F(n) 為第 n 月兔子對數。

F(1) = 1（初始一對幼兔）
F(2) = 1（第二月長大但未生產）
n ≥ 3：F(n) = F(n-1) + F(n-2)
　　—— 上月存活兔 F(n-1) + 新出生兔 F(n-2)（兩月前的兔子現已性成熟）

數列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765...

五種演算法實作比較

1. 遞迴（教學用，指數級）

long long fib_rec(int n) {
    if (n <= 2) return 1;
    return fib_rec(n-1) + fib_rec(n-2);  // O(φ^n) 極慢
}

2. 迭代雙變數交換（線性，O(1) 空間）

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

原文採用的技巧：f1 = f1 + f2; f2 = f1 + f2; 實際上每圈產生兩項，輸出時每行印四個數值。

3. 矩陣快速冪（對數級，O(log n)）

利用 [F(n+1), F(n)]^T = M^n · [1, 0]^T，其中 M = [[1,1],[1,0]]。

typedef struct { long long a, b, c, d; } Mat;
Mat mul(Mat x, Mat y) {
    return (Mat){ 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 };
}
Mat mpow(Mat base, long long exp) {
    Mat 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_log(long long n) {
    if (n <= 2) return 1;
    Mat M = {1,1,1,0};
    Mat R = mpow(M, n-2);
    return R.a + R.b;  // F(n) = R[0][0]*1 + R[0][1]*0
}

4. Binet 封閉式公式（常數時間，浮點誤差風險）

long long fib_binet(int n) {
    const double phi = (1 + sqrt(5)) / 2;
    return (long long)round(pow(phi, n) / sqrt(5));
}

n > 70 時 double 精度不足，需用 long double 或大整數庫。

5. 快速倍增法（無矩陣，純整數）

// 回傳 (F(n), F(n+1))
void fib_pair(long long n, long long *fn, long long *fn1) {
    if (n == 0) { *fn = 0; *fn1 = 1; return; }
    long long a, b;
    fib_pair(n >> 1, &a, &b);
    long long c = a * (2*b - a);
    long long d = a*a + b*b;
    if (n & 1) { *fn = d; *fn1 = c + d; }
    else       { *fn = c; *fn1 = d; }
}
long long fib_fast(long long n) {
    long long fn, fn1;
    fib_pair(n, &fn, &fn1);
    return fn;
}

完整可執行程式（含溢位檢查）

#include <stdio.h>
#include <limits.h>

unsigned long long fib_iter_safe(int n, int *overflow) {
    unsigned long long a = 1, b = 1;
    if (n <= 2) return 1;
    for (int i = 3; i <= n; ++i) {
        if (ULLONG_MAX - a < b) { *overflow = 1; return 0; }
        unsigned long long c = a + b;
        a = b; b = c;
    }
    return b;
}

int main() {
    printf("月份  兔子對數\n");
    for (int m = 1; m <= 90; ++m) {  // ULL 最大到 F(93)
        int ov = 0;
        unsigned long long val = fib_iter_safe(m, &ov);
        if (ov) { printf("%3d  溢位\n", m); break; }
        printf("%3d  %20llu\n", m, val);
    }
    return 0;
}