На этом шаге мы рассмотрим несколько примеров рекурсии.
Говорят, что объект или понятие рекурсивны, когда в его состав входят более простые или меньшие подобные ему элементы. Природа даёт множество примеров этого свойства (см. рисунок 1).
Рис.1. Примеры рекурсивных объектов
Например, ветку дерева можно считать основой для меньших веток, которые отходят от неё и, в свою очередь, состоят из других, меньших, веток, и так далее до почки, листа или цветка. Строение кровеносных сосудов или рек тоже подобно структуре ветвления деревьев, когда бOльшая структура содержит подобные ей элементы, но в меньших масштабах. Другой родственный рекурсивный пример - капуста романеско (Romanesco broccoli), где отдельные маленькие цветки явно напоминают всё растение. Другие примеры включают горные цепи, облака или рисунок кожи животных.
Рекурсия также появляется в искусстве. Известный пример - эффект Дросте (Droste-effect), который представляет собой картинку, повторяющуюся внутри себя. Теоретически такой процесс бесконечен, но на практике он, конечно же, заканчивается, когда наименьшая картинка становится настолько малой, что занимает всего один пиксель в цифровом изображении. Создаваемый компьютером фрактал - ещё один тип рекурсивного изображения. Например, треугольник Серпиньского состоит из трёх меньших идентичных треугольников, которые затем делятся ещё на три меньших. Бесконечно повторяя этот процесс, мы обнаружим, что каждый маленький треугольник имеет ту же структуру, что и оригинал. И последний, классический пример иллюстрации рекурсии - набор кукол-матрёшек. В этом ремесле каждая кукла имеет такой размер, чтобы уместиться внутри большей куклы. Отметим, что рекурсивный объект - это не одна полая кукла, а вся вложенная коллекция кукол. Таким образом, рекурсивное мышление предполагает, что вся коллекция кукол может быть описана как одна-единственная (наибольшая) кукла, которая содержит внутри себя меньшую коллекцию кукол.
Хотя в приведённых примерах рекурсивные объекты - явно материальные, рекурсия встречается и в огромном числе абстрактных понятий. В этом отношении рекурсию можно понимать как процесс определения понятий через их собственные определения. Таким способом можно выразить многие математические формулы и определения. Самые очевидные примеры - последовательности, n-й член которых задаётся некоторой формулой или процедурой, использующей предыдущие члены. Рассмотрим следующее рекурсивное определение:
sn = sn-1 + sn-2 (1.1)
Формула говорит о том, что член последовательности sn - это просто сумма двух предыдущих членов sn-1 и sn-2. Сразу видно, что формула рекурсивна, так как определяемый ею объект s появляется в обеих частях уравнения. Таким образом, элементы последовательности явно определяются через самих себя. Кроме того, заметьте, что рекурсивная формула (1.1) описывает не конкретную последовательность, а целое семейство последовательностей, где каждый её член есть сумма двух предыдущих членов. Чтобы задать конкретную последовательность, мы должны предоставить дополнительную информацию. В данном случае достаточно задать любые два члена последовательности. Как правило, чтобы определить такую последовательность, достаточно задать два первых её члена. Например, если s1 = s2 = 1, то мы получим последовательность
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...,
Последовательности могут начинаться и с члена s0.
Последовательность s можно считать функцией, которая в качестве аргумента получает положительное целое число n, а возвращает n-й член этой последовательности. В этом случае функция Фибоначчи, обозначенная просто как F, может быть определена как:
1, если n = 1
F(n) = 1, если n = 2 (1.2)
F(n - 1) + F(n - 2), если n > 2.
Всюду мы будем использовать для описания функции такие обозначения, когда определения включают два типа выражений или случаев. Начальные условия (base cases) соответствуют случаю, когда результат функции может быть получен тривиально без привлечения значений функции от дополнительных параметров. По определению, начальные условия для чисел Фибоначчи - это F(1) = 1 и F(2) = 1. Рекурсивные условия (recursive cases) представляют собой более сложные рекурсивные выражения, включающие обычно определённую функцию от предыдущих значений входных параметров. Функция Фибоначчи имеет одно рекурсивное условие: F(n) = F(n - 1) + F(n - 2), если n > 2. Начальные условия необходимы для получения из рекурсивных условий конкретных значений членов последовательности. В заключение следует сказать, что рекурсивное определение может содержать несколько начальных и рекурсивных условий.
На следующем шаге мы закончим изучение этого вопроса.
