java - 如何为组合编写递归函数

Question

我正在复习递归函数，并且我了解如何编写基本函数，但我的学习指南上有一个我不明白的问题。

。为计算 nCr 的名为 Combinations 的递归函数编写代码。假设 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