Понимание рекурсии с использованием всех возможных комбинаций в массиве

Question

Я пытаюсь понять рекурсию с помощью нескольких примеров.Я нашел этот пример печати всех возможных комбинаций r элементов в заданном массиве размером n с использованием рекурсии.

Печать всех возможных комбинаций r элементов в данном массиве размера 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}.)

Есть только 2 возможности:

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) элементов - поэтому есть

способов выбора такой комбинации.