C 語言遞歸計算組合數 C(n, r)

遞歸公式

已知 C(n, r) = C(n, r-1) * (n - r + 1) / r，基例 C(n, 0) = 1。

代碼實現

int compute(int n, int r) {
    if (r == 0) return 1;
    return compute(n, r - 1) * (n - r + 1) / r;
}

注意事項

• 整數除法需保證分子能被分母整除（組合數性質保證），但中間結果可能溢出 int，大數場景用 long long 或任意精度庫。
• 遞歸深度為 r，r 較大時棧溢出風險，可改寫為迭代：

long long comb(int n, int r) {
    long long res = 1;
    for (int i = 1; i <= r; ++i) {
        res = res * (n - i + 1) / i;
    }
    return res;
}