Рекурсивные алгоритмы применяются в генерации комбинаторных последовательностей для решения задач, например:

• Генерации k-элементных подмножеств. 1 В качестве первого компонента подмножества можно выбрать любые компоненты, начиная с самого первого и кончая (n – k + 1)-м. 1 После фиксации индекса первого компонента подмножества нужно сделать выбор k – 1 компонент из оставшегося набора компонентов, имеющих индексы больше первого. 1 Затем процедура повторяется. 1 Выбор последнего компонента означает достижение последнего рекурсивного уровня, и можно приступить к обработке найденного подмножества (например, выполнить его анализ или отправить на печать). 1
• Генерации всех перестановок в лексикографическом порядке. 2 Идея рекурсии заключается в том, что на i-й позиции должны побывать все элементы массива p с i-го по n-й. 2 Для каждого из этих элементов должны быть получены все перестановки остальных элементов, начиная с (i + 1)-го места, в лексикографическом порядке. 2 После получения последней из перестановок, начиная с (i + 1)-й позиции, исходный порядок элементов должен быть восстановлен. 2