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

Question

我试图在几个例子的帮助下理解递归。我发现这个例子使用递归打印r给定大小数组中所有可能的元素组合。n打印给定大小为 n 的数组中 r 个元素的所有可能组合。他们正在使用表达式背后的想法：我在这里试图理解的是这个表达的概念意义。我读过不同的文章，但找不到令人满意的解释。使用此表达式的数学或实际示例将非常有帮助。

Answer 1

首先，数学中的组合有不同的表示法：

使用第一个，你的公式是

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

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

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

Let是集合中元素C的任意组合。 rS

（特别是，按照刚刚介绍的示例，您可以想象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}）。

如果Ccontains x，则从剩余元素(r - 1)（即2在我们的示例中）中选择剩余(n - 1)元素（即{a, b, c, d, e, f}在我们的示例中） - 所以有

如何选择这样的组合。

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

如何选择这样的组合。