C語言遞歸實現：組合數計算 C(m,n)

數學定義

C(m,n) = C(m-1,n) + C(m-1,n-1)，邊界：C(m,0)=C(m,m)=1。

遞歸實現

#include <stdio.h>

long long comb(int m, int n) {
    if (n == 0 || n == m) return 1;
    return comb(m-1, n) + comb(m-1, n-1);
}

int main() {
    int m, n;
    printf("輸入 m n: ");
    scanf("%d%d", &m, &n);
    if (n > m || n < 0) { printf("參數錯誤\n"); return 1; }
    printf("C(%d,%d) = %lld\n", m, n, comb(m, n));
    return 0;
}

效能問題與優化

• 純遞歸重複計算極多，時間複雜度 O(2^n)，m=30 即明顯卡頓。
• 記憶化（備忘錄）：用二維陣列緩存結果，降至 O(m·n)。
• 動態規劃（帕斯卡三角）：自底向上填表，空間可優化為 O(n)。
• 乘除公式：C(m,n) = m*(m-1)*...*(m-n+1) / n!，單次循環 O(n)，注意溢位順序（先除後乘或用長整型）。

動態規劃版本（推薦工程用）

long long combDP(int m, int n) {
    if (n > m-n) n = m-n;  // 利用對稱性減少循環
    long long *dp = calloc(n+1, sizeof(long long));
    dp[0] = 1;
    for (int i=1; i<=m; i++) {
        int upper = (i < n) ? i : n;
        for (int j=upper; j>=1; j--)
            dp[j] += dp[j-1];
    }
    long long res = dp[n];
    free(dp);
    return res;
}

溢位界限

• long long (64-bit) 最大 ≈ 9.22e18，C(66,33) ≈ 7.2e18 尚可，C(67,33) 溢位。
• 大數需用任意精度庫（GMP）或自製大整數。

組合數遞歸是教科書級遞歸範例，但實際應用必須採用動態規劃或乘除公式，並注意資料型別範圍。