如何为组合编写递归函数

Question

我正在查看递归函数,我理解如何编写基本函数,但我对我的学习指南有一个我不明白的问题.

.编写一个名为Combinations的递归函数的代码,用于计算nCr.假设nCr可以如下计算:

nCr = 1 if r = 0 or if r = n and
nCr = (n-1)C(r-1) + (n-1)Cr

有人可以帮我解决这个问题,还是以外行的方式解释一下？谢谢!

Answer 1

这个问题确实包含了所有信息.它告诉你如何计算nCr - 并且在很多时候,你通过计算另一个nCr(具有较小的参数)来计算它.所以你的功能可能如下所示:

int nCr(n, r) {
  if (r == 0 || r == n) return 1;  // stop recursion, we know the answer.
  return nCr(n-1, r-1) + nCr(n-1, r); // the answer is made of the sum of two "easier" ones
}

这就是我尽可能的翻译.让我们通过计算看看它在实践中是如何运作的

nCr(4,2)
= nCr(4-1, 2-1) + nCr(4-1, 2)
= nCr(3, 1) + nCr(3, 2)
= nCr(3-1, 1) + nCr(3-1,0) + nCr(3-1, 2-1) + nCr(3-1, 2)
= nCr(2, 1) + nCr(2,0) + nCr(2,1) + nCr(2,2)
= nCr(1, 0) + nCr(1,1) + 1 + nCr(1,0) + nCr(1,1) + 1
= 1 + 1 + 1 + 1 + 1 + 1
= 6

当然我们已经知道了:

nCr(4,2) = (4 * 3) / (2 * 1) = 6