Java 如何为组合编写递归函数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20485602/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do I write a recursive function for a combination
提问by onTheInternet
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.
我正在学习递归函数，我了解如何编写基本函数，但是我对我的学习指南有一个我不明白的问题。
. Write code for a recursive function named Combinations that computes nCr. Assume that nCr can be computed as follows:
. 为名为 Combinations 的计算 nCr 的递归函数编写代码。假设 nCr 可以计算如下：
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!
有人可以帮助我解决这个问题或用外行的术语解释吗？谢谢！
采纳答案by Floris
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:
这个问题确实包含了所有信息。它告诉您如何计算 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
}
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
Of course we knew that already:
当然，我们已经知道：
nCr(4,2) = (4 * 3) / (2 * 1) = 6
回答by Paperwaste
A recursive function includes calls to itself and a termination case
递归函数包括对自身的调用和终止情况
in your example nCr = 1 if r = 0 or if r = nforms the termination
在你的例子中nCr = 1 if r = 0 or if r = n形成终止
and (n-1)C(r-1) + (n-1)Cris the recursion
并且(n-1)C(r-1) + (n-1)Cr是递归
so your code should look somethink like this
所以你的代码应该看起来像这样
int nCR(int n, int r){
if (r == 0 || r == n){
return 1; //terminate
}
else{
return nCr(n-1, r-1) + nCr(n-1, r); //recursive calls
}
}
