***

Рекурсия для чайников

Как герой Мольера не знал, что он разговаривает прозой, так и мы зачастую не знаем, что пользуемся рекурсией.

Научно выражаясь:

Рекурсия — метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса.
Другими словами, рекурсия — частичное определение объекта через себя, определение объекта с использованием ранее определённых. Рекурсия используется, когда можно выделить самоподобие задачи.

Математики и программисты хорошо знают, что такое рекурсия и активно ею пользуются.

В математике

Факториал целого неотрицательного числа n обозначается n! и определяется как
n!=n;(n-1)! при n>0 и n!=1 при n=0

Практически все геометрические фракталы задаются в форме бесконечной рекурсии.

Треугольник Серпинского.

В программировании:

Рекурсия — вызов функции из неё же самой (обычно с другими значениями входных параметров), непосредственно или через другие функции (например, функция А вызывает функцию B, а функция B — функцию A). Количество вложенных вызовов функции называется глубиной рекурсии. Мощь рекурсивного определения объекта в том, что такое конечное определение способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.

Рекурсия в физике

Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала: в них образуются два коридора из затухающих отражений зеркал.

Другим примером бесконечной рекурсии является эффект самовозбуждения (положительной обратной связи) у электронных схем усиления, когда сигнал с выхода попадает на вход, усиливается, снова попадает на вход схемы и снова усиливается. Усилители, для которых такой режим работы является штатным, называются автогенераторы.

Рекурсия в лингвистике

См. также: Рекурсия (лингвистика)
Способность языка порождать вложенные предложения и конструкции. Базовое предложение «кошка съела мышь» может быть за счёт рекурсии расширено как Ваня догадался, что кошка съела мышь, далее как Катя знает, что Ваня догадался, что кошка съела мышь и так далее. Рекурсия считается одной из лингвистических универсалий, то есть свойственна любому естественному языку. Однако, в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии — пираха, которое отмечает лингвист Дэниэл Эверетт (англ.)

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

Весьма популярна шутка о рекурсии, напоминающая словарную статью:
РЕКУРСИЯ
см. рекурсия

«У попа была собака…» - типичная рекурсия

У попа была собака, он её любил
Она съела кусок мяса, он её убил
В землю закопал,
Надпись написал:
«У попа была собака, он её любил
Она съела кусок мяса, он её убил
В землю закопал,
Надпись написал:

Несколько рассказов Станислава Лема посвящены казусам при бесконечной рекурсии:

Рассказ о сепульках («Звёздные дневники Йона Тихого»), в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки».
Следующие краткие сведения:
«СЕПУЛЬКИ — важный элемент цивилизации ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКАРИИ».
Я последовал этому совету и прочёл:
«СЕПУЛЬКАРИИ — устройства для сепуления (см.)».
Я поискал «Сепуление»; там значилось:
«СЕПУЛЕНИЕ — занятие ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКИ».
Лем С. «Звёздные дневники Ийона Тихого. Путешествие четырнадцатое.»

Рассказ о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).

Рекурсия в изобразительном искусстве.

Эффект Droste - термин для изображения специфического вида рекурсивного изображения. Изображение включает уменьшенный собственный вариант самого себя. Этот более малый вариант после этого показывает даже более малый вариант себя, и так далее. Практически это продолжается пока разрешение изображения позволяет уменьшает размер. Термин был введен в честь Droste, голландского какао.

Рекурсия продемонстрирована в Print Gallery Эшера. В этой известной работе молодой человек осматривает картину. На картине мы видим среднеземноморский порт. Картина нарисована с использованием некоторой эллиптической кривой, так, что одно из зданий в картине, которое является галерей, в то же самое время формирует окружение галереи. Эшер не смог нарисовать место, где галерея в картине сливается с реальной галереей и поэтому нарисовал белую заплату в середине, которая содержит вензель Эшер и подпись. В это центральной точке должна появиться была проявиться рекурсия картины.
http://botinok.co.il/node/29842
Математики Де Смит и Ленстра из Лейденского университета разрешили математически проблему и реконструировали картину для того, чтобы заменить белую заплату.

Рекурсия в сюжете.
Первым романом, удивившим читателей приемом рекурсии, был "Дон Кихот". Сервантес все время пытался смешивать два мира: мир читателя и мир книги. У Сервантеса главный процесс не просто книга, но книга плюс читатель.В шестой главе цирюльник, осматривая библиотеку Дон Кихота, находит книгу Сервантеса и высказываетсуждения о писателе. Вымысел Сервантеса рассуждает о нем. В начале девятой главы сообщается, что роман переведен с арабского и что Сервантес купил его на рынке. Наконец, во второй части романа персонажи уже прочли первую часть.

Элементы использования рекурсии находим еще раньше у Шекспира. Гамлет ставит спектакль, где в упрощенном варианте описываются события трагедии.

"Мастер и Маргарита" - один из наиболее ярких рекурсивных романов. Развивается одна алгоритмическая схема, используемая в разных процессах: Мастер и Маргарита, Иешуа и Пилат, Воланд и компания.Тема Иешуа и Пилата рекурсивно вызывается из темы Мастера и Маргариты. Кроме того, здесь такжеиспользуется прием "книга в книге". Мастер пишет роман об Иешуа и Пилате, текст которого сливаетсяс текстом книги "Мастер и Маргарита".

"Сто лет одиночества" Г. Маркеса. Рекурсивно повторяются события поколений семейства Буэндиа. Последний из рода Буэндиа заканчивает расшифровывать рукопись волшебника Мелькиадеса, кото-рая оказывается тем же описанием "Ста лет одиночества". По мере прочтения поднимается и нарастает ураган. Прочитывается последняя страница, книга заканчивается, и все исчезает в бушующем смерче.

В литературе, живописи, музыке рекурсивные приемы сочетаются с описаниями ощущений тревоги и страха. Возможно, рекурсивные повторы связаны с чувством глубины и создают такой же психологический эффект, как и тот, который возникает,когда человек заглядывает в пропасть. Это опасно туда можно упасть. Отсюда и чувство тревоги. Но иногда так хочется туда заглянуть. Там может быть что-то неведомое, а может быть, даже то, что человек все время ищет. Поэтому все же так тянет заглянуть в таинственную глубину. А некоторые даже отваживаются исследовать глубины рекурсии.

Психотропные вещества, воздействуя на мозг, могут вызывать рекурсивные видения. Человек может видеть себя со стороны, летать, может увидеть кого-то, наблюдающего за собой. Такие видения часто возникают при приеме наркотиков-галлюциногенов, в частности LSD. Цюрихский профессор В. А. Штоль описывает опыт на себе по приему этого наркотика."Вначале галлюцинации были элементарно просты: лучи, сноп лучей, дождь, кольца, вихрь, петли, во-дяные брызги, облака и так далее. Потом галлюцинации стали более сложными: арки, ряды арок, бесконечное море крыш, виды пустынь, горные террасы, мерцающие огни, звездное небо невиданной красоты.Эти сложные картины то и дело перемежались первоначальными элементарными образами... Интересно,что все видения состояли из бесконечного числа повторений одних и тех же элементов: многочисленных искр, кругов, арок, окон, огней и т.д. Ни разу не видел я чего-нибудь в единственном числе, наоборот,одно и тоже все время повторялось в различных сочетаниях... "

С рекурсией, возможно, связана еще одна неясная медицинская проблема, получившая название "синдром Стендаля". Французский писатель Стендаль путешествовал по Италии. Во Флоренции, рассматривая картины художников эпохи Возрождения, он внезапно потерял сознание. В наше время аналогичные случаивстречаются все чаще у посетителей флорентийских музеев. Возможно следующее объяснение. Живопись итальянского Ренессанса началась с картин флорентийца Джотто, который первым применил перспективу и тем самым стал создавать объемные изображения. Перспектива - это тоже рекурсивная схема. Художник мысленно делит пространство на срезы и для каждого применяет одну и ту же процедуру плоского нанесенияна паверхность картины, но с коэффициентом уменьшения. Искусство Джотто продолжили флорентийскиемастера. В картинах Гирландайо, Боттичелли, Козимо Медичи для подчеркивания перспективы появляются повторяющиеся и резко уменьшающиеся ступени лестниц, деревья, арки, фигуры. Часто изображаются окна или открытые двери, за которыми открывается своя картина, а в ней возможна другая.

Представим ощущения зрителя в музее. Погружаешься в давние времена, в картины, в детали картин, деталидеталей. Следишь взглядом за повторяющимися ступенями древнего замка, арками и колоннами храмов,фигурами людей. Рассматриваешь детали переднегоплана и тут же видишь другие детали заднего плана.Сознание рекурсивно качается туда и сюда, туда -в глубину - и обратно, туда и обратно, туда... В какой-то момент действительность перестает существовать, и где-то в мозге недремлющий страж сознаниявызывает спасительный шок.

ПОСЛЕ НАПИСАННОГО:

В посте использованы книги Анатолия Анисимова, статьи из русской и английской Википедии, диссертация университета Гронингена, сборник статей NOTICES OF THE AMS

ПОСЛЕ P.S.

Тема неисчерпаема, как и сама рекурсия. Я даже не упомянул о рекурсии в музыке, архитектуре, психологии и т.д.

Другие статьи в литературном дневнике:

• 10.09.2012. ***
• 07.09.2012. ***