«Фрактальной называется структура, состоящая из частей, которые в каком-то смысле подобны целому».
Фрактальный повтор
Когда какое-то действие необходимо повторить большое количество раз, используются циклические процессы и процедуры. Один шаг цикла называется итерацией.
Серийное производство есть «итерация по шаблону», т. е. на каждом шаге вычислений идет возврат к начальному условию. Здесь каждый новый цикл стартует «от печки». «Итерацию по шаблону» использует программист, когда ему нужно вывести сто раз на экран текст «Iteration». Вместо стократного повторения одной и той же команды вывода текста программист создает цикл, который повторяется сто раз, и сто раз выполняет то, что написано в «теле цикла».
Совсем иное дело, когда итерация имеет формат рекурсии. В этом случае результат предыдущего шага итерации становится начальным условием для следующего. Так, например, положение и скорость тела в каждый момент времени определяются через положение и скорость тела в предыдущий момент времени. Визуально рекурсия иллюстрирует рекламный трюк — эффект Дросте.
Эффект Дросте — термин ввел в конце 1970-х годов журналист Нико Схепмакер по названию голландской марки какао фирмы Droste, которая использовала этот эффект на упаковке своей продукции в 1904 году.
Эффект рекурсии достигается таким образом: на фотографии размещается уменьшенный вариант той же фотографии или объекта с этой фотографии, на уменьшенной копии размешается еще более уменьшенная фотография, и так далее
Иллюстрация эффекта Дросте на примере видеоинтерпретации картины Эшера Galeria degrabados, 1956
Хорошей математической иллюстрацией рекурсии являются числа Фибоначчи. Этот термин придумал в XIX веке французский математик и автор многих популярных математических головоломок Эдуард Люка. Числа Фибоначчи — первая известная в Европе рекурсивная последовательность. Многие из тех, кто изучал математику, естественные науки или искусства, слышали о Фибоначчи исключительно благодаря следующей задаче из главы XII его «Liber abaci» («Книга абака», 1202):
«Некий человек поместил пару кроликов в огороженное со всех сторон место. Сколько пар кроликов произойдет от этой пары за год, если предположить, что каждый месяц каждая пара порождает новую пару, которая еще через месяц становится способна приносить потомство ?»
Суть проста. Сначала у нас одна пара. Проходит первый месяц, первая пара порождает еще пару, их становится две. Проходит второй месяц, взрослая пара порождает еще одну юную пару, а молодая пара тем временем подрастает. Итак, у нас три пары. Проходит третий месяц, каждая из двух взрослых пар порождает еще по паре, а юная пара подрастает; итак, у нас уже пять пар. Проходит четвертый месяц, каждая из трех взрослых пар порождает еще по паре, а две юные пары подрастают, следовательно, у нас уже восемь пар. После пяти месяцев у нас по юной паре от каждой из пяти взрослых пар плюс три подрастающие пары — всего тринадцать пар.
Теперь мы уяснили закономерность и знаем, как получить число взрослых пар и юных пар и общее число пар кроликов в каждый последующий месяц. Предположим, нас интересует только число взрослых пар в каждый конкретный месяц. Это число состоит из числа взрослых пар в предыдущий месяц плюс количество юных пар (к данному моменту успевших повзрослеть) в тот же предыдущий месяц. Однако количество юных пар месяц назад на самом деле равно количеству взрослых пар в позапрошлом месяце. Итак, в каждый конкретный месяц, начиная с третьего, количество взрослых пар просто-напросто равно сумме количества взрослых пар за два предшествующих месяца. Итак, количество взрослых пар подчиняется последовательности