如何为组合编写递归函数 [英] How do I write a recursive function for a combination

问题描述

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

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

这篇关于如何为组合编写递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！