Рекурсия

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

Классическое определение из Википедии:

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

Треугольник Серпинского — фрактал, один из двумерных аналогов множества Кантора предложенный польским математиком Серпинским в 1915 году. Также известен как «решётка» или «салфетка» Серпинского.

В литературе

Чаще всего используется рекурсия как метод в программировании, в физике и лингвистике, и вот в последнем случае все куда интереснее и понятнее: вместо математики используется способность любого языка порождать вложенные конструкции. Кому из нас в детстве не рассказывали сказку про белого бычка?

Сказка про белого

Сказка про белого бычка — русская поговорка, которая означает бесконечную историю. Относится к категории докучных сказок, в которых многократно повторяется один и тот же фрагмент текста. Такая сказка похожа на цепь с большим количеством повторяющихся звеньев, количество которых зависит только от воли исполнителя или слушателя.

— Сказать ли тебе сказку про белого бычка?
— Скажи.
— Ты скажи, да я скажи, да сказать ли тебе сказку про белого бычка?
— Скажи.
— Ты скажи, да я скажи, да чего у вас будет, да докуль это будет! Сказать ли тебе сказку про белого бычка?

У Г. Г. Маркеса в «100 лет одиночества» упоминается «Сказка про белого каплуна»:

Это была игра — из тех, что никогда не кончаются: ведущий спрашивал остальных, хотят ли они послушать сказку про белого каплуна, и, если ему отвечали «да», он говорил, что не просил ответить «да», а просил ответить, рассказать ли им сказку про белого каплуна, если ему отвечали «нет», он говорил, что не просил говорить «нет», а просил ответить, рассказать ли им сказку про белого каплуна; если все молчали, ведущий говорил, что не просил молчать, а просил ответить, рассказать ли им сказку про белого каплуна; и никто не мог уйти, потому что ведущий говорил, что не просил их уходить, а просил ответить, рассказать ли им сказку про белого каплуна. И так без конца, по замкнутому кругу, целые ночи напролет.

Сепульки

В романе С. Лемма «Звёздные дневники Ийона Тихого», в «Путешествии четырнадцатом» герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки»:

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

Еще

У Лема же есть серия рассказов «Кибериада», и в одном из них фигурирует разумная машина, которая обладает достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей. Итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей.

У С. Лукьяненко в повести «Царь, царевич, король, королевич…» есть эпизод, где персонажи листают повесть «Царь, царевич, король, королевич…», чтобы узнать будущее:

Пока я размышлял, стоит ли принимать такие странные извинения, Кубатай полистал книжку и громко, выразительно прочитал: — «Пока я размышлял, стоит ли принимать такие странные извинения, Кубатай полистал книжку и громко, выразительно прочитал: — Пока я размышлял, стоит ли принимать такие странные извинения, Кубатай полистал книжку и громко, выразительно прочитал: — Пока я размышлял...» Быстрым движением Холмс выхватил у Кубатая томик.

Нельзя не вспомнить сказку-песню «У попа была собака…». Здесь рекурсия ограничена объемом доступных ресурсов, то есть размером доски, на которой писал поп.

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

В искусстве

М. Эшер часто эксплуатировал в творчестве рекурсии. 

Эффект Дросте

Одна из визуальных форм рекурсии называется «Эффект Дросте» — по названию марки какао Droste, которая использовала этот эффект в рекламе.

Вот еще несколько красивых работ с использованием этого эффекта, но кто автор, установить не удалось. Если знаете, напишите нам.

В интернете

На Абсурдопедии

Лаконичное объяснение, эксплуатирующее все ту же шутку «чтобы понять, что такое рекурсия, надо понять, что такое рекурсия».

На Башорге

xxx: поделись рекурсией своей, и она к тебе не раз еще вернется

Tomas:
Я офигел когда во 2-ю больницу пришел. Дурдом полнейший.
MoSt:
хы
Tomas:
Дык я иду в 14 кабинет, там написано, что типа надо иди в 34, в 34 написано идти в 31, а в 31 написано идти в 14. Вот это как можно назвать?
MoSt:
рекурсия

Тема на локальном форуме:
Представь: ты очнулся голый, днем, на полу сортира на вокзале. Рядом никого. В кулаке зажаты 100 рублей. Ты ничего не можешь вспомнить - ни как тебя зовут, ни где ты живешь и как тут оказался.
Твои действия?
ххх:
ждать в сортире, пока кто зайдет. отмудохать его головой об унитаз. забрать одежду и все его вещи. в кулак ему сунуть 100 рублей
ууу:
рекурсия бля
zzz:
Всё встает на свои места.
nnn:
Больше не буду заходить в сортиры на вокзале.

<Fen-Omen> Настоящая рекурсия начнется, если вы попытаетесь вернуть себе диск, который давали другу год назад...

Tr1a m3ra > Самая тупая, блять, рекурсия - когда девушка пытается помочь справиться с депрессией, причной которой она сама и является...

Салат «рекурсивный»: помидоры, огурцы, салат…

>> Сегодня пытался объяснить маме, что такое рекурсия.
>> Привёл пример: ходил по квартире и сам себя звал по имени. Кажется, мама поняла всё по-своему.
>> Кстати, она психиатр.

Рекурсивный кот.

Еще немного примеров

Требуется расклейщик объявлений для расклейки объявлений о приеме на работу расклейщиков объявлений о приеме на работу расклейщиков объявлений.

Коктейль «рекурсивный»: 30% воды, 20% спирта, 50% рекурсивного коктейля.

Цитата из книги английского математика Дж. Литлвуда «Mathematician’s miscellany», выпущенной в 1957 году:

Однажды научный журнал Spectator объявил среди читателей конкурс на тему «Что бы вы с наибольшим удовольствием прочли, раскрыв утреннюю газету?». Приз получил ответ: «Наш второй конкурс. Первый приз во втором конкурсе этого года присуждён мистеру Артуру Робинсону, остроумный ответ которого без натяжки должен быть признан наилучшим. Его ответ на вопрос «Что бы вы с наибольшим удовольствием прочли, раскрыв утреннюю газету?» был озаглавлен «Наш второй конкурс», и состоял в следующем: «Первый приз во втором конкурсе этого года присуждён мистеру Артуру Робинсону, остроумный ответ которого без натяжки должен быть признан наилучшим. Его ответ на вопрос „Что бы вы с наибольшим удовольствием прочли, раскрыв утреннюю газету?“ был озаглавлен „Наш второй конкурс“, но из-за лимитирования бумаги мы не можем напечатать его полностью»

Masacra и его КОШ

Dungeons & Dragons — настольная ролевая игра.