问题描述
我正在处理递归函数，我理解如何编写基本函数，但我对我的学习指南有一个我不明白的问题。
I am going over recursive functions and i understand how to write basic ones, but I have a question on my study guide that I dont understand.
。编写名为Combinations的递归函数的代码，用于计算nCr。假设nCr可以如下计算：
. Write code for a recursive function named Combinations that computes nCr. Assume that nCr can be computed as follows:
nCr = 1 if r = 0 or if r = n and
nCr = (n-1)C(r-1) + (n-1)Cr
可以有人请帮我解决这个问题或以外行的方式解释一下吗？谢谢！
Can someone please help me through this or explain in layman's terms? Thank you!
推荐答案
这个问题确实包含了所有信息。它告诉你如何计算nCr - 并且在很多时候，你通过计算另一个nCr（使用较小的参数）来计算它。所以你的函数可能如下所示：
The question really has all the information. It tells you how to compute nCr - and that a lot of the time, you compute it by computing another nCr (with smaller arguments). So your functions might look like this:
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
}
那是按字面意思翻译。让我们看看它在实践中是如何运作的，通过计算
That's translating as literally as I can. Let's see how that works in practice, by computing
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
这篇关于如何为组合编写递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！