На этом шаге мы наметим план дальнейшего изложения.
Рекурсия широко используется в комбинаторике - разделе математики, изучающем подсчёт на дискретных множествах объектов и играющем важнейшую роль в анализе алгоритмов. Последующие шаги посвящены рекурсивным решениям вычислительных задач подсчёта, цель которых - сложение определенного числа элементов, объектов, вариантов, понятий и т. д. Общая стратегия заключается в разбиении подлежащих подсчёту элементов на несколько непересекающихся подмножеств с последующим сложением количеств в каждом из них. С точки зрения рекурсии исходная задача должна разбиваться на несколько меньших подзадач, а её результатом должна быть сумма результатов этих меньших подзадач.
В предыдущих шагах мы уже встречались с несколькими из таких задач. Например, вычисление суммы первых положительных целых чисел можно понимать как подсчёт числа квадратных блоков треугольных структур, как показано на рисунке 2 шага 4. В последующих шагах мы изучим две рекурсивные стратегии подсчёта битов, опирающиеся на две разные декомпозиции.
Мы увидим, что несколько из широко известных рекурсивных функций связано с фундаментальными комбинаторными понятиями. Например, факториал, мощность и биномиальные коэффициенты связаны с перестановками, размещениями (с повторами) и сочетаниями соответственно. Кроме того, во многих комбинаторных задачах возникают ещё и числа Фибоначчи. Далее мы будем выводить эти функции, расчленяя соответствующие задачи подсчёта, а не их математические формулы и определения. Хотя все эти задачи - чисто математические, мы будем решать их, используя те же понятия, приёмы и методики, что были изложены в предыдущих шагах.
Наконец, поскольку решения задач подсчёта либо просты для программирования, либо уже появлялись в нашем изложении, то здесь практически не будет программного кода. В этом смысле их основная цель - побудить к рекурсивному мышлению при решении разного рода вычислительных задач.
На следующем шаге мы рассмотрим перестановки.
