c++ - 我写来找到计算NCR的此函数有什么问题？

我尝试使用这种关系来递归地找到nCr的值:

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

对于6C2的 call ，我得到12而不是15。我试图进行跟踪，但是我得到了正确的答案。任何输入表示赞赏!谢谢

最佳答案

考虑当执行comb(6, 2)时会发生什么。在第一个递归调用中，返回表达式变为:

return (5 / 2) * comb(6, 1);

(5 / 2)将进行整数除法，并给出不正确的2。
由于nCr的最终答案实际上可以保证得到的结果是整数，因此您可以通过在将其除以任何分母之前简单地计算所有分子来修正方程式，如下所示:

return (n - r + 1) * comb(n , r - 1) / r ;

这是demo。
请注意，如果您担心分子值溢出int，则可以重新构造方程式，或者使用其他公式来更早地取消术语。