使用数组中的所有可能组合了解递归

Question

我试图通过几个例子来理解递归。我发现这个例子是使用递归在给定的r大小的数组中打印n元素的所有可能组合。

Print all possible combinations of r elements in a given array of size n.

他们正在使用表达背后的想法：

我在这里想要理解的是这个表达的概念意义。我读过不同的文章但找不到令人满意的解释。

使用此表达式的数学或实际示例将非常有用。

Answer 1

首先，数学中的组合有不同的符号：

使用第一个，你的公式是

它的左侧表示：我们可以从r元素集中选择n元素的方式。

让S成为一组n元素。让x成为它的最后一个元素，所以设置S就是例如

+-------------+---+
| a b c d e f | x |
+-------------+---+

让C是来自集合r的S元素的任意组合。

（特别是，按照刚才介绍的例子，你可以想象r = 3和n = 7 - 作为集合是{a, b, c, d, e, f, x}。）

只有两种可能性：

1. C包含x（例如C = {a, d, x}），或者
2. C不包含x（例如C = {a, d, e}）。

如果C包含x，那么剩下的(r - 1)元素（即我们的例子中的2）是从剩余的(n - 1)元素中选择的（即在我们的例子中来自{a, b, c, d, e, f}） - 所以有

如何选择这种组合的方法。

如果C不包含x，那么所有r元素都是从剩余的(n - 1)元素中选择的 - 所以有

如何选择这种组合的方法。