c++对二项式系数递归函数的误解

Question

代码：

#include<stdio.h>
int binomialCoeff(int n, int k)
{
  // Base Cases
  if (k==0 || k==n)
    return 1;
 else
  return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}
int main()
{
    int n = 5, k = 2;
    printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k));
    return 0;
}

我想我能理解基本情况。当我们对 n 使用 0 且 k=n 时，结果为 0!/0!这是= 1。所以我们return 1。Formula

但是我看不懂这部分代码：

 return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);

n 的值为 5，k 的值为 2，我得到结果 10。（在公式中替换时）。formula 但为什么我们使用加法？

还有一件事。为什么当我从键盘上设置“n”和“k”时程序不工作？像这样：

int main()
{
    int n,k;
    cin>>n;
    cin>>k;
    printf("Value of C(%d, %d) is %d ", n, k, binomialCoeff(n, k));
    return 0;
}

Answer 1

But why we use аddition?

与其说是编程问题，不如说是数学问题，众所周知recursive formula for binomial coefficient calculation。您的程序中正是使用了这个公式。

Why the program does't work when i set "n" and "k" from the keyboard

除了您使用 std::istream 作为输入并使用 printf 作为输出之外，代码看起来是正确的。到底什么不起作用？您是否输入 n >= k？

Answer 2

return binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);

还记得Pascal Triangle吗？它使用加法的递推公式。

但是我可以看到你不是在构建这个三角形，而是在使用递归时一次又一次地递归地尝试计算一些二项式系数。记住已经计算出的结果可能会大大提高您的程序性能。你的第二个问题可能是这样的：

Why the program does't work when i set "n" and "k" from the keyboard. like this:

它应该可以工作，但是如果您输入相当大的 n 和 k，您的程序可能需要很长时间才能完成。运行时间复杂度为O(n²)。使用 n > 30 您可能会注意到执行时间很长。

Answer 3

二项式系数的一个性质是： C(n, k) 可以写成 C(n-1,k-1) + C(n-1,k) 对于所有 1 <= k <= n-1.

所以 C(3,2) = C(2,1) + C(2,2) 或者 3 = 2 + 1

这是您分享的简单递归示例中使用的内容。

关于你的第二个问题，不知道你为什么会有问题。

c++对二项式系数递归函数的误解

c++ misunderstanding of binomial coeficient recursive function

c++

recursion

binomial-coefficients