純 C 語言遞歸實現組合數計算：C(m,n) 源碼解析

組合數 C(m,n) = m! / (n!(m-n)!) 遞歸定義：C(m,n) = C(m-1,n) + C(m-1,n-1)，邊界 C(m,0)=C(m,m)=1。本文給出純 C 遞歸實現，並分析效率與優化方向。

遞歸實現代碼

#include 

// 遞歸計算 C(m,n)
int Combination(int m, int n) {
    if (n == 0 || n == m) return 1;      // 邊界
    return Combination(m-1, n) + Combination(m-1, n-1); // 遞歸公式
}

int main() {
    int m, n;
    printf("請輸入 m: "); scanf("%d", &m);
    printf("請輸入 n: "); scanf("%d", &n);
    if (n < 0 || n > m) {
        printf("錯誤：n 必須在 0..m 範圍內\n");
        return 1;
    }
    int result = Combination(m, n);
    printf("C(%d,%d) = %d\n", m, n, result);
    return 0;
}

運行示例

請輸入 m: 5
請輸入 n: 2
C(5,2) = 10

遞歸樹與時間複雜度分析

• 遞歸樹為二叉樹，高度 m，葉子節點數 = C(m,n)。
• 時間複雜度 O(C(m,n))，指數級增長。m=30, n=15 即需 ~1.5 億次調用，極慢。
• 空間複雜度 O(m)（遞歸棧深度）。

優化方案

1. 記憶化搜索（DP 表）

int dp[100][100]; // 假設 m < 100
int CombMemo(int m, int n) {
    if (n == 0 || n == m) return 1;
    if (dp[m][n]) return dp[m][n];
    return dp[m][n] = CombMemo(m-1, n) + CombMemo(m-1, n-1);
}

時間/空間均降為 O(m·n)。

2. 迭代動態規劃（帕斯卡三角形）

int CombDP(int m, int n) {
    int *C = calloc(n+1, sizeof(int));
    C[0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = (i < n ? i : n); j > 0; j--)
            C[j] += C[j-1];
    }
    int res = C[n];
    free(C);
    return res;
}

空間優化至 O(n)，時間 O(m·n)。

3. 直接公式 + 約分（大數情況）

利用 C(m,n) = ∏(m-n+i)/i (i=1..n)，每步約分避免溢出，配合大整數庫處理極大值。

總結

遞歸實現雖簡潔直觀，但**指數級複雜度僅適合教學演示極小數據**。實際工程必須採用**動態規劃（O(mn)）或迭代公式（O(n)空間）**。理解遞歸到 DP 的轉化過程，是算法設計的核心功力之一。