Рекурсия

To iterate is human, to recurse, divine

— James O. Coplien, Bell Labs

Это, например, рекурсия. А может быть, даже фрактал.

Cyanide and Happiness

Рекурсия — см. «Рекурсия».

А вообще

Рекурсией программисты на своём мунспике называют вызов функцией самой себя прямо(ананизм) (в теле функции расположен вызов себя) или косвенно (функция вызывает функцию, которая вызывает функцию, которая… и в одной из этих функций расположен вызов самой первой функции). У хорошей, годной рекурсии должно быть и условие для выхода из рекурсии, иначе получается зацикливание, причём, в отличие от обычного цикла, рано или поздно приводящее к переполнению стека (см. ниже). Типичным примером функций, использующих рекурсию, являются вычисление факториала и функция Аккермана. В более общем смысле, включение некоторой сущностью самой себя целиком (см. пример с зеркалами ниже). Более сложный вариант: «Чтобы понять рекурсию, нужно сперва понять рекурсию».

Переполнение стека

Как говорилось выше, это закономерный результат хуёвонаписанной рекурсии. Если говорить просто, то каждой программке, при запуске, выделяется место в ОЗУ, в этом месте находится и сам код программы, область данных, а так же стек вызовов, эта штука является списком вызовов функции. при каждом вызове стек увеличивается, добавляя в себя запись о том, откуда была вызвана функция, чтобы после её завершения, вернуться обратно. После каждого выхода из функции, стек снова уменьшается на одну запись. Проблема в том, что его вместимость ограничена и если функция начнет бесконтрольно вызывать саму себя, то это приведёт к пиздецу — стек переполнится и после этого ОС, непрерывно бдящая за всеми процессами, заявит, что «дальше Бога нет» и аварийно остановит программу.

Помимо своего матанного и программистского значения, рекурсия — мем, используемый в наших интернетах в основном среди читателей башорга. Уйдя в массы, мем утратил своё специфичное значение и используется для описания любой рвущей шаблон ситуации. Чаще всего слово «рекурсия» всплывает ассоциацией в мозгу планктонины либо при упоминании бесконечности как меры мощности множества, либо при столкновении с логическим парадоксом (так, зарегистрированы случаи непроизвольного произнесения слова «рекурсия» при упоминании парадокса лжеца).

Наблюдение рекурсии

Это как тако внутри тако? Да, это такое тако внутри тако внутри супер-тако внутри ресторана «Тако Белл» внутри KFC в супермаркете внутри сна.

— South Park

Так называемый Droste Effect.

Ещё один

Вообще древнейший из примеров применения рекурсии IRL связан ещё с изобретением зеркала. Установив два зеркала параллельно и строго напротив друг друга, внутри можно увидеть классическую рекурсию. А при особом упорстве и склонности к магии — и неиллюзорную кучу глюков. Но мы же не ищем лёгких путей. Поэтому если вам внезапно нечем будет себя занять, то можете поэкспериментировать и с другими методами получения рекурсии:

• Просто включите веб-камеру и наведите её на экран монитора. Или просто обычную видеокамеру, наведя на показывающий с неё телевизор. В последнем случае (повращав камеру) можно убедиться в том, что даже телевизор способен неиллюзорно тормозить.
• Тот же самый спецэффект можно получить и с меньшим бюджетом, воспользовавшись программой записи видео с экрана (или программой-лупой).
• Также её можно наблюдать в игре Portal, если создать два портала один перед другим.
• Кстати об играх. В The Stanley Parable в одной из концовок ГГ слышит, как голос в его голове (закадровый рассказчик) говорит о том, что ГГ его слышит.
• А ещё можно поюзать Radmin или что-то подобное для управления удаленным десктопом и приконнектиться к локалхосту.
• Православный и легкодоступный способ.

1. На своем компе активируем Team Viewer.
2. Заходим на отдаленную машину через удаленное подключение к рабочему столу.
3. На удаленной машине также запускаем Team Viewer
4. Подключаемся к своему исходному компу.

Получите каноничную рекурсию и, если комп слабый, нарастающие тормоза системы.

• Если и этого нет под рукой, то подобную рекурсию можно произвести вручную. Откройте любой графический редактор (например, тот же MS Paint) и с детским задором, высунув язык, без остановки поочерёдно жмакайте на клавиатуре Ctrl+Print Screen и Ctrl+V.
• Человека от обезьяны отличает отнюдь не абстрактное мышление, как любили догматически утверждать марксисты, а способность к мышлению рекурсивному.

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

Рекурсия и цикл

Не стоит путать рекурсию и цикл (возможно, бесконечный). Отрицательный пример — тоже пример, рассмотрим выражение:

1. Начальник всегда прав. 2. Если начальник не прав, смотреть п. 1.

Оно является циклом с плохим условием, а не рекурсией. Дональд Кнут гарантирует. Можно ли это переделать в рекурсию? Да:

Приказ № 1. Начальник всегда прав. Если начальник не прав, см. Приказ № 1.

С точки зрения процесса, это по-прежнему цикл. Чтобы процесс стал рекурсивным, можно сделать так:

п1. Если начальник не прав, то см. п1. и начальник всегда прав.

Более понятный вариант:

111: А можешь мне, как гуманитарию, объяснить разницу между бесконечным циклом и бесконечной рекурсией?
222: Но вот смотри:
"У царя был двор, во дворе стоял кол,
На колу мочало, начинай сначала" - это бесконечный цикл.
"У попа была собака, он ее любил,
Она съела кусок мяса - он ее убил,
В яму закопал, крест поставил, написал: ..." - это бесконечная рекурсия.

— anekdot.ru

ЧНЯР

Не следует также путать рекурсию и заколдованный круг (также известный как «тупик» или «взаимная блокировка»). Отличие между ними в том, что рекурсия не имеет точки выхода, а тупик — точки входа. Именно к взаимным блокировкам относится кое-что по тексту статьи. Это не может быть рекурсией, так как не предполагает повторяющихся действий. Исхитрившись один раз добыть пароль из ящика, мы разрываем круг. Ведь никому не придёт в голову обозвать рекурсией цикл while (false)?.. Подобная ситуация также известна как проблема курицы и яйца.

Примеры:

• «Установите драйвера для CD-ROM, находящиеся на нашем компакт-диске».
• «Для выхода в Интернет скачайте из Интернета нашу программу».
• «Windows не смог найти драйверы для устройства Модем. Поискать в интернете?»
• WinRAR.rar
• «Keyboard not found. Press F1 to continue» (BIOS). На самом деле это — лаконичная просьба проверить, правильно ли клавиатура подключена. Иногда f1 очень даже нажимается.
• «Если у Вас украли кредитную карту, позвоните по телефону, указанному на оборотной стороне кредитной карты».
• «Смысл жизни — в достижении её цели, цель жизни — в наполнении её смыслом» (или, как вариант, — «Смысл жизни в том, чтобы найти смысл жизни»).
• «Уйти, себя избавить памяти о близких, чтобы, уйдя, избавить память близких о себе»
• При Советской власти в крупных городах (>100000) наняться на работу можно было только при предоставлении справки о прописке, а прописаться можно было только при наличии справки с места работы, что доставляло субъекту множество разных эмоций.
• Рассказ Айзека Азимова «…Вставьте шплинт А в гнездо Б…» о роботе, который должен был складывать других роботов и механизмы по инструкциям, записанным у него в памяти, но самого робота нужно было тоже складывать по прилагающейся к нему инструкции.

Примеры рекурсии

В BIOS.

Таки да, это не единичный случай.

Тот самый WinRAR

• Бюрократия разрастается, чтобы удовлетворить нужды разрастающейся бюрократии.
• Программа «Средство отправки отчетов об ошибках» неожиданно завершила работу. Отправить отчет об этой ошибке?
• Библии можно верить, потому что в Библии написано, что Библии можно верить. (ЛПП: В Библии такое не написано)
• При вводе в Google слова «рекурсия», он будет говорить: «Возможно, вы имели в виду: рекурсия».
• Тренинги личностного роста: «чтобы добиться уверенности в себе, надо начать верить в себя».

Кстати, пример с клавиатурой немного особенный: USB-клавиатура иногда всё же может послать на материнскую плату нужный сигнал при нажатии кнопки F1. При этом некоторые материнки (некоторые под 370 сокет) всё-таки сначала выдадут ошибку, а по нажатию кнопки адекватно воспримут сигнал и прогрузятся.

В кино и мультипликации

Рекурсия и правило 34 от Oglafа

Учёные доказали, что утверждения, начинающиеся со слов «учёные доказали», никогда ими не доказывались.

— Рекурсия и взаимоисключающие параграфы

• В фильме «12 друзей Оушена» представлен интересный пример рекурсии: Джулия Робертс сыграла героиню, которая по сюжету фильма некоторое время неубедительно играла Джулию Робертс.
• Легендарный актёр первой половины XX века Борис Карлофф однажды играл гангстера, которого страшно раздражает то, что его всё время принимают за Бориса Карлоффа.
• В сериале «Сверхъестественное» в восемнадцатой серии четвертого сезона предсказатель предсказывает то, что он предскажет… И когда Дин читает рукопись предсказания, он недоумевает. Дин: «Я сижу в прачечной и читаю о себе, сидящем в прачечной и читающем о себе, сидящем в прачечной…»
• В этом вашем «Хаусе» в конце второго сезона Хаус видит галлюцинацию, в которой он, в свою очередь, тоже видит галлюцинацию. Кто смотрел, поймёт.
• В фильме «Быть Джоном Малковичем» Джон Малкович, роль которого играет Джон Малкович, проникает в сознание Джона Малковича, в котором он обнаруживает кучу Джонов Малковичей.
• В фильме «Адаптация», поставленном по сценарию Чарли Кауфмана(который, к тому же сценарист предыдущего фильма), Чарли Кауфман пишет сценарий про то, как Чарли Кауфман пишет сценарий.
• В фильме «Космические яйца» два мудозвона, не зная, что делать дальше по сюжету, решают посмотреть кино «Космические яйца».
• В серии «Most Wanted» Бивис говорит: «Я сделаю татуировку в виде задницы на моей заднице».

Тот самый кадр из «Паранойи». Video Feedback в действии.

• В фильме «Паранойя», в момент настройки главным героем камеры наблюдения (на 1:09:52), можно обнаружить рекурсию (скрин прилагается).
• В одной из серий киножурнала «Ералаш» есть абсолютно тупой эпизод, где лоли сломя голову мчится домой к зомбоящику, сметая всё на своём пути, чтобы посмотреть всё тот же киножурнал «Ералаш»
• Что, видимо, спизжено из заставки к Симпсонам, где Симпсоны сломя голову разными путями добираются домой смотреть «Симпсонов». В одном из couch gag показывается, что вселенная Симпсонов находится внутри атома, находящегося в голове Гомера Симпсона. И да, эту заставку он видит по телевизору.
• И ещё: «Симпсоны» — мультик в мире «Футурамы», а «Футурама» — мультик в мире «Симпсонов».
• Ну, «Начало» же! «Inception», десу! Весь фильм главные герои только и занимаются тем, что смотрят сон, в котором смотрят сон, в котором смотрят сон (просто так можно ужать час в минуту)
• В фильме «В пасти безумия» Джона Карпентера про глобальный пиздец главный герой в конце идет в кинотеатр смотреть фильм «В пасти безумия». Да и вообще, кино местами повествует самое себя, когда герои читают отрывки книги, по которой снят этот фильм.
• В серии Гриффинов 8x11 Питер не понимает, почему у Мег в спальне преступник, и поэтому он берет телепрограмму и смотрит в описание серии, в которой он находится.
• В махо-сёдзе «Cardcaptor Sakura» (в OVAшке) сам сериал оказывается результатом режиссёрских трудов подруги Сакуры, отправленных на телевидение.
• В фильме «Наказание» одна из героинь меняется сознанием с телом матери девятнадцатилетней давности, проживает её тогдашнюю жизнь и меняется сознанием уже с собой. И таких примеров в фильме масса.
• В фильме Немое кино, созданном в жанре немого кино, рассказывается о попытке снять немое кино.
• Одна из серий «Масяни» «День сурком» состоит из рекурсии чуть более, чем полностью.
• Да и сам «День сурка» является не бесконечным циклом, а рекурсией, из которой ГГ всё же, начитавшись достаточно книг и наигравшись на пианино, сумел выйти через хороший, годный пикап.
• В пиндостанском шоу «1000 способов умереть» один из героев смотрит по телевизору «1000 способов умереть».
• В фильме «Частный детектив, или операция „Кооперация“» в конце невъебенно счастливый Харатьян на крутой тачке подвозит папу своего героя к кинотеатру с афишей сего же фильма.
• Сюжет фильма «Новый кошмар Уэса Крейвена» заключается в том, что во время съёмок нового фильма про Фредди Крюгера начинают погибать люди из съёмочной группы. В финальной сцене главная героиня находит сценарий только что закончившегося фильма.
• В клипе группы Nero «Me And You» парень находит в подсобке торгового-развлекательного центра заброшенный игровой автомат. В конце игры парень видит в ней себя самого стоящим за игровым автоматом.
• В одной из серий «Чёрного Плаща» Гога рекламирует по телевизору кукурузные хлопья, на коробке которых изображено, как Гога рекламирует кукурузные хлопья, на коробке которых изображено, как Гога рекламирует кукурузные хлопья. Ну ты понел.
• В одной из серий «Бригады» Саша Белый видит, как возле ресторана снимают кино про бандитов под названием «Бригада». При выходе он замечает, как бандитов на съёмочной площадке по сценарию скручивает ОМОН. Буквально через несколько секунд то же самое происходит с Сашей Белым и его бригадой.
• Некоторые эпизоды сериала «Доктор Кто» буквально состоят из чистой рекурсии — например, машина времени материализуется внутри самой себя. В Рождественском эпизоде 2014 года также присутствует рекурсия: герои просыпаются, чтобы понять, что спят, снова просыпаются и так много раз..
• Ещё в советском фильме «31 июня», снятом по нетленке Джона Бойнтона Пристли, есть забавный момент, когда главный герой находит на столике томик Пристли с произведением, по которому снято кино… и ловит от этого истинное наслаждение, когда до него доходит непередаваемое ощущение попаданца.
• Впоследствии эту шутку скопировали в ремейке «Графа Монте-Кристо», где в конце фильма граф Туманский к вящему удовольствию главзлодея дарит ему книгу, по мотивам которой снят фильм.
• В ещё одном идейно правильном кино про Алису Коля Герасимов в будущем «станет самым обыкновенным инженером и изобретёт самую обыкновенную машину времени»… с использования которой именно им и начинается сюжет кино. Больше всего доставляет то, что предсказание это добуквенно соответствует книжке, по которой снят фильм.
  • Чушь! В фильме говорится, что «Садовский станет обыкновенным инженером и изобретет самую обыкновенную машину времени.» А Герасимов же будет писать стихи. Да и в книге Коля даже не Герасимов, а Наумов. Но и не Наумов, по предсказанию, изобретет машину времени, а Коля Сулима. Наумов же, по книге, станет строителем домов. Так что, как пример рекурсии — правильно, но к реальным фильму и книге не имеет отношения никак.
• В мультсериале про Кота Леопольда есть эпизод, где главный герой смотрит по телевизору этот же мультсериал.
• Терминатор же. В далёком будущем Джон Коннор знает, как бороться с машинами, поэтому Скайнет раз за разом посылает в прошлое терминаторов-убийц. Уничтожая их, Коннор и получает столь опасные для машин навыки.
• Сюжет британского хоррора «Треугольник» есть рекурсия верхом на рекурсии и рекурсией же погоняющая. Любители идеи «петли времени» вполне могут посмотреть.
• Кино 2015 года «Он снова здесь» о воскресшем Гитлере снято по одноимённой книге. Книга фигурирует в сюжете фильма, причём герои опять-таки решают экранизировать её, в результате чего концовка фильма оказывается действом на съёмочной площадке.
• В мультсериале «Маска» (сиквел одноименного фильма) ГГ, озвученный Джимом Керри, встречает… Джима Керри и даже танцует на пару с ним.
• Диалог в поезде из винрарной кинокомедии Леонида Гайдая «Спортлото-82»:

-Почему вы ложку под подушкой держите?
- А где мне ее держать?
- В стакане.
- Но стакан под подушку не положишь!
- А зачем вам стакан под подушку класть?
- Правильно, ни к чему. Вот поэтому, я положил одну ложку, понимаете?!
- Угу, понимаю... И все же, зачем вы положили ложку под подушку!?

• «Рик и Морти», 6 эпизод 2 сезона. Рик Санчез создаёт микровселенную, служащую ему батарейкой. В какой-то момент в ней рождается учёный, также создающий свою нано-вселенную, в которой ещё один учёный… Ну вы поняли. А в последнем эпизоде того же сезона после титров есть сцена, в которой мы видим мистера Жопосранчика, который смотрит титры только что закончившейся серии и бурно обсуждает происходящее.
• Все фильмы трилогии «Матрица» начинаются со знаменитых падающих циферок, которые состоят из других мелких циферок, и так N раз. Алсо, изначальный сценарий предполагал, что мир Зиона — часть многоуровневой симуляции, и всякая попытка выбраться из Матрицы в неё бы и приводила.
• В сериале «Black Mirror» огромное количество рекурсии. Во-первых, тут тоже часто используется тема многоуровневых искусственных миров, из которых нет выхода. Во-вторых, куча отсылок на предыдущие серии — типа трансляции этого же сериала по ТВ под видом кинохроники или музея орудий убийств из старых эпизодов.
• Фильм «Патруль времени» (англ. Predestination) — прекрасный пример рекурсии. ГГ тут злодей, отец и мать себя самого...
• В анимационном фильме «Путешествие в подсознание» на 10 минуте 20 секунде мне лень объяснять отредактируйте пожалуйста

В играх

• Вышеупомянутый Portal.
• The Stanley Parable имеет концовку, в которой ГГ слышит, как голос в его голове (закадровый рассказчик) говорит о том, что ГГ его слышит.
• В Hitman: Blood Money можно найти картины с изображением безликого человека в строгом костюме и красном галстуке (то бишь самого Хитмана).
• Если в Half-Life разбить ящик, оттуда может выпасть диск с надписью «Half-Life 2.0».
• В мире игр компании Rockstar существует компания Rockstar, чей логотип встречается на каждом углу.
• Чувак из Постала- бывший сотрудник корпорации Running with Scissors. Угадайте, как называется компания-разработчик серии Postal?
• В новомодном Goat Simulator есть возможность рогами и копытами разгромить офис Coffee Stain Studios, студию авторов игры.
• В Doom Eternal встречается здание офиса ID Software разработавшей игру,Думгай может поиграть в Doom и Doom II в которых главным героем является тот же Думгай.
• В легенде всех западных имиджбордов — поигрульке про Генри Стикмина — Henry Stickmin Collection в одной из концовок имеется просто огромных размеров танк, и ГГ должен как-то его угнать. Одним из вариантов является просмотр на местном аналоге ТыТрубы (NewTube) туториала, в котором другой пользователь тоже доходит до этого места, после чего начинает повествовать о том что произойдёт если нажать на вариант со всё тем же туториалом, после чего начнёт воспроизводить слова того кто нажал на этот туториал, после чего начнёт говорить от его лица, доходя до того же момента и (ВНЕЗАПНО) тоже начиная повторять слова тогоктио нажал на тутос… Ну и короче это может продолжаться бесконечно, иногда прерываясь рекламой тамошних аналогов Facebook, Twitter и т. д. За вашим терпением даже следит какой-то секундомер и выдаёт достижения за рекорды.

Из жизни братьев наших меньших

xkcd о рекурсии

• Хаскель состоит из рекурсии чуть менее, чем полностью.
• Scheme же состоит из рекурсии чуть более, чем полностью.
• Реакция на слово «рекурсия» типичного ПеХаПе-программиста.
• В этом вашем OCaml есть специальное слово «rec», которое вставляется перед названием функции, если программист хочет показать, что она будет рекурсивной.
• В Фортране тоже: функция рекурсивна, если имеет атрибут recursive; в противном случае имя функции — это идентификатор возвращаемого значения.
• Ассемблер FASM написан на самом ассемблере FASM.

Показанные в этом разделе примеры у программистов называют «бесконечным рекурсивным циклом», а в программировании к рекурсии (которая и так может быть банальным «добавить к Х единичку каждый цикл», то есть Х=Х+N) еще и прописывается «пока не…», оно же «условие выхода из рекурсии».

В архитектуре

Расположенная на Исаакиевском соборе статуя Монферрана, держащего в руке Исаакиевский собор

На западном фасаде Исаакиевского собора в Петербурге расположилась огромная статуя архитектора Монферрана, который держит в руке модель построенного им собора (по-видимому, с такой же статуей на западном портике). Алсо, внутри собора на иконостасе преподобный Исаакий держит в левой руке свиток, на развёрнутой части которого изображён Исаакиевский собор (с таким иконостасом и свитком внутри и т. д.).

В законодательстве

• Из Земельного кодекса Российской Федерации (ст. 5):

собственники земельных участков — лица, являющиеся собственниками земельных участков

— http://base.consultant.ru/cons/cgi/online.cgi?req=doc;base=LAW;n=148550

• Из Закона о защите информации (ст. 16):

1. Защита информации представляет собой принятие правовых, организационных и технических мер, направленных на:

1) обеспечение защиты информации от неправомерного доступа, уничтожения, модифицирования, блокирования, копирования, предоставления, распространения, а также от иных неправомерных действий в отношении такой информации;

— http://www.consultant.ru/cons/cgi/online.cgi?req=doc&base=LAW&n=201168&fld=134&dst=100014,0&rnd=0.38172715064138174

• Из Закона об авторском праве и смежных правах (ст. 8):

Не являются объектами авторского права:

государственные символы и знаки (флаги, гербы, ордена, денежные знаки и иные государственные символы и знаки);

— http://www.consultant.ru/document/cons_doc_LAW_2238/d13b797504e844b618f544036b1a38124b464f13/

• Из действующей конституции КНР:

Статья 33. Все лица, имеющие гражданство Китайской Народной Республики, являются гражданами Китайской Народной Республики

— https://chinalaw.center/constitutional_law/china_constitution_revised_2018_russian/

• Прошедшему обряд посвящения в полицейские, чтобы получить форму, нужно предъявить удостоверение, где он сфотографирован в форме.

• Народные депутаты Верховной Рады отличили эротику от порнографии, обосновав, что: «…продукция порнографического характера — продукция, которая содержит порнографию».

• В фашистских концлагерях попытка самоубийства каралась смертной казнью.

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

В геральдике

Первым в этом списке, естественно, идет российский герб. Причем, естественно, только современный его вариант. Скипетр, который орёл держит в правой лапе, увенчан небольшим двуглавым орлом, который в свою очередь также держит скипетр…

Рекурсивный герб

Также, на бывшем гербе Хабаровского края сидит медведь, который держит в руках герб Хабаровска, на котором медведь и тигр держат дореволюционный герб Хабаровска, где в левом верхнем углу расположен герб Камчатки.

В гидравлике

Эпическая рекурсия: сжатие гидравлического пресса в гидравлическом прессе гидравлическим прессом

В музыке

Рекурсивный клип: Gabin — «Doo Uap Doo Uap Doo Uap»

Еще один: Kylie Minogue — «Come Into My World»

Björk — «Bachelorette», рекурсия с глубиной вложенности 3

• Pink Floyd, альбом «Ummagamma», 1969 год/
• Ирландский расовый Bog Down in the Valley.
• Верный пример рекурсии из этого вашего Сплина:

И мудрец сошел с ума, набрал 01,
И по вызову явился незнакомый господин.
И господин сошел с ума, набрал 01,
И по вызову явился незнакомый господин.
И господин сошел с ума, набрал 01,
И по вызову явился незнакомый господин.
И господин сказал…

И ещё «Человек и дерево»:

Человек, проглотивший дерево,
превращается в дерево, проглотившее человека.
Человек, который проглотил дерево,
превращается в дерево, проглотившее человека.

• Песня «Человек» советской группы «Центр». Чтобы понять, надо прослушать целиком.

• Детская песенка:

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

А также целый жанр докучных сказок.

• Незабвенная «Put The Lime In The Coconut»

• А еще у Наутилуса песня «Ни кому ни кабельность»:

Я набрал знакомый номер, а в нём короткие гудки, это — мой телефонный номер, видимо, с кем-то уже говорю

• У Максима Леонидова в песне «Девочка-виденье» есть такие слова:

Я оглянулся посмотреть, не оглянулась ли она,
Чтоб посмотреть, не оглянулся ли я

• У Высоцкого в «Песне о мангустах» (надо слушать целиком)

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

В Педивикии

Рекурсия в классической фотографии: Д. Бальтерманц — маршал С. Буденный у любимого портрета.

Копипаста оттуда:

Введение в вопрос: в 2006 году в одной из статей Википедии был создан (разными участниками в течение примерно полугода) некий текст. Через некоторое время его принялись копировать авторы статей в реферируемых журналах. При внимательном изучении статьи выяснилось, что источниками текст толком и не подтверждён — были проставлены запросы. Нетрудно догадаться, что запросы были заменены теми самыми источниками, которые из Википедии текст и взяли, благо, совпадение текстов по понятным причинам очень близкое:). Я указал, что в данной ситуации эти источники не являются авторитетными, так как сами заимствовали текст из Википедии. Были высказаны возражения, которые вкратце можно передать как «ВАК — это серьёзно, там всё всегда проверяется, ничего неправильного там опубликовано быть не может, дата публикации ни о чём не говорит, статья в научном журнале — бесспорный абсолютный АИ».

В зависимости от ориентации, развитие баттхерта, расширение рек поноса до ширины Енисея, участие, учащение периода рекурсии возможно тут.

Собственно статья, по поводу которой шли метания говн — Содружество непризнанных государств.

В книгах

• В повести Пейсателя «Царь, царевич, король, королевич…» есть доставляющий эпизод (в отличие от самой книги), где персонажи решают пролистать повесть «Царь, царевич, король, королевич…», чтобы узнать будущие события:

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

• У Атомного Татарина:

Люди бывают свиньи, шакалы и люди.

• Из литературных анекдотов, ошибочно приписываемых Д. Хармсу:

Гоголь переоделся Пушкиным, пришел к Пушкину и позвонил. Пушкин открыл ему и кричит: «Смотри, Арина Родионовна, я пришел!»

• В рассказе «Название согласно контракту не приводится» ГГ (юрист) выступает в роли защитника рассказа, где он, ГГ (юрист) выступает в роли защитника рассказа, где он (юрист) выступает… Кроме того, работает правило 34:

В юридической атмосфере почти невозможно дышать. Этот воздух<…> На ней лежала та самая распечатка. Я открыл первую страницу. Первым предложением было «В юридической атмосфере почти невозможно дышать. Этот воздух…»

• Аналогично у юмориста Аркадия Арканова в книжке «Рукописи не возвращаются»: в финале появляется тетрадь с романом, который начинается с тех же слов, что и книга.

В помещении редакции журнала «Поле-полюшко» частенько пахло газом.<…> «В печенках они у меня со своей литературой!» — подумал Рапсод Мургабович, машинально раскрыл тетрадь в красном кожаном переплете и прочитал: «В помещении редакции журнала „Поле-полюшко“ частенько пахло газом…»

• • Обложка собрания сочинений Арканова также рекурсивна: на ней изображён он сам, держащий в руках собрание сочинений, на обложке которого изображён Арканов, держащий собрание…
• У Григория Горина «Дом, который построил Свифт».

Эстэр (открыла книгу, начала медленно читать вслух). «19 ОКТЯБРЯ 1745 ГОДА НЕ СТАЛО ДЖОНАТАНА СВИФТА. НАКАНУНЕ ВЕЧЕРОМ ОН ИСПЫТЫВАЛ СТРАННОЕ БЕСПОКОЙСТВО, ТОЧНО ПРЕДЧУВСТВОВАЛ СВОЙ ПОСЛЕДНИЙ МИГ. ПО ВОСПОМИНАНИЯМ БЛИЗКИХ ДЕКАНА, ОН ДАЖЕ НЕОЖИДАННО ЗАГОВОРИЛ ПОСЛЕ ДОЛГИХ ЛЕТ МОЛЧАНИЯ. ПЕРВОЕ СЛОВО, ПРОИЗНЕСЕННОЕ СВИФТОМ, БЫЛО СЛОВО „КОГДА?“».
Распахнулась дверь. На пороге стоял Свифт. Эстэр испуганно захлопнула книгу.
Свифт. Когда?

• У Маяковского в стихотворении «Бруклинский мост» наблюдается хороший, годный пример рекурсии:

И дальше картина моя без загвоздки
по струнам-канатам, аж звездам к ногам.
Я вижу — здесь стоял Маяковский,
стоял и стихи слагал по слогам.

• У Льюиса Кэрролла «Алиса в Зазеркалье».

Черный Король мне снится. Но он спит и видит во сне, будто я сплю и вижу во сне, что он спит и видит меня во сне… Видно, я никогда не доберусь до конца.

• У Антуана де Сент-Экзюпери в «Маленьком принце», правда, с выходом из рекурсии:

— Что это ты делаешь? — спросил Маленький принц.
— Пью, — мрачно ответил пьяница.
— Зачем?
— Чтобы забыть.
— О чем забыть? — спросил Маленький принц; ему стало жаль пьяницу.
— Хочу забыть, что мне совестно, — признался пьяница и повесил голову.
— Отчего же тебе совестно? — спросил Маленький принц, ему очень хотелось помочь бедняге.
— Совестно пить! — объяснил пьяница, и больше от него нельзя было добиться ни слова.

• Создатели Death Note выпускали мангу Bakuman в журнале «Weekly Shonen Jump», в нем же выпускали свои произведения и ГГ манги.

• У Козьмы Пруткова:

Где начало того конца, которым заканчивается начало?

• У Стругацких в «Понедельник начинается в субботу» есть хороший, годный пример рекурсии, который к тому же хорошо ложится на язык матана. Речь идет об эксперименте Саши Привалова с неразменным пятаком Наины Киевны Горыныч, хозяйки Изнакурножа. Всякий раз, когда Саша расплачивался этим пятаком, последний неизменно возвращался в его карман. Таким образом, в данном случае мы имеем рекурсивную функцию, которая принимает на входе пятак и возвращает этот же пятак плюс какой-нибудь мелкий ништяк, например, стакан газировки или номер «Соловецкой правды». Местный милиционер, сержант Ковалев, утверждал даже, что были попытки скопить таким образом на «Запорожец».

• У Григория Остера:

Возьми густой вишневый сок
И белый мамин плащ.
Лей аккуратно сок на плащ —
Получится пятно.
Теперь, чтоб не было пятна
На мамином плаще,
Плащ надо сунуть целиком
В густой вишневый сок.

Возьми вишневый мамин плащ
И кружку молока.
Лей аккуратно молоко —
Появится пятно.
Теперь, чтоб не было пятна
На мамином плаще,
Плащ надо сунуть целиком
В кастрюлю с молоком.

Возьми густой вишневый сок
И белый мамин плащ.
Лей аккуратно…

Рекурсивные акронимы

Про PHP
PHP — от англ. Personal home page — личная домашняя страничка. Так-то! Впоследствии для пущей солидности была изобретена другая интерпретация: PHP: Hypertext Preprocessor. Она содержит рекурсию вовсе не потому, что PHP-разработчики любят рекурсию, а скорее потому, что подогнать нормальный акроним к имеющимся буквам было весьма затруднительно.

Про PNG
Официально PNG — Portable network graphics. Однако формат создавался как альтернатива патентнотролльскому GIF, поэтому на самом деле верна неофициальная интерпретация.

Бородатые линуксоиды обожают рекурсивные бэкронимы:

• Linux — Linux is not unix
• GNU — GNU is not unix
• WINE — WINE is not an emulator
• PINE — PINE is not elm
• LAME — LAME ain’t an MP3 encoder
• Gajim — Gajim is a jabber instant messenger
• PNG — PNG is not GIF
• Hurd — HIRD of Unix-Replacing Daemons, где HIRD — HURD of Interfaces Representing Depth.

В общем, и Микрософт тоже:

• XNA — XNA’s not acronymed
• Bing — Bing is not Google

Внезапно:

• VISA — Visa International Service Association
• АСКА — акционерная страховая компания «АСКА»
• VES — VES Electric Spain
• FGHI — FGHI Global Headlight Ignited
• MEGA — MEGA Encrypted Global Access

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

• Простейший пример рекурсивной функции, вычисляющей факториал на Common Lisp’е:

(defun fact (x) (if (> x 1) (* x (fact (- x 1))) 1))

• И рекурсия на BASIC’е:

10 gosub 10

• И двойная на C:

uint f(uint x) {
  return x?--x?f(--x)+f(++x):++x:x;;
}

В браузере

• В Firefox введите (однако в мобильной версии не работает):

chrome://browser/content/browser.xul

Потом снова и снова…

С миру по нитке

Подпольная рекурсия

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

Бомба всегда падает в эпицентр.

<DaGGeR> У нас на обед — салат «Рекурсивный» : помидоры, огурцы, салат.

100219

мама папе: а это что за рваные деньги тут лежат?
папа: ну скопились рваные деньги. А скотча, чтобы заклеить, дома нет. А чтобы купить скотч, нужны деньги. А они рваные, нужно сначала заклеить. Вот и лежат...

416177

1: Я подумаю. Иди потролль кого-нибудь.
2: Я подумаю. Иди потролль кого-нибудь.

Ты мне сам говорил тебе не доверять. У меня нет оснований тебе не верить.

— Ты где деньги берёшь?
— Жена даёт.
— А жена где берёт?
— Из тумбочки.
— А в тумбочку кто кладёт?
— Я кладу.

В: Какой вопрос может являться ответом сам на себя?
О: «Какой вопрос может являться ответом сам на себя?»

Parchom: «Цена на топливо выросла потому что увеличилась цена на топливо, которое используют бензововозы при доставке топлива.»

420965

Сайт росреестра запрещённых сайтов попал в росреестр запрещённых сайтов за то, что содержал информацию о запрещённых сайтах.

Что означает «Б» в имени Бенуа Б. Мандельброта? — Бенуа Б. Мандельброт.

— Шутеечка про «Отца фрактальной геометрии»

Алсо

Хорошая, годная рекурсия.

Из одного из рисовач-тредов Нульчана

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

Однажды научный журнал Spectator объявил среди читателей конкурс на тему «Что бы вы с наибольшим удовольствием прочли, раскрыв утреннюю газету?».

Приз получил ответ:

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

— пруф

• Известно, что в системах с ограниченным объёмом оперативной памяти (компьютер, мозг быдлокодера…) неограниченная или недостаточно ограниченная рекурсия может привести к stack overflow с малопредсказуемыми, но не всегда неприятными последствиями. Знатоки Хацкеля обычно дружелюбно поплёвывают в данную сторону людей лямбдой.
• Логический парадокс «я лгу» косвенно относится к рекурсии. Это так называемые автореферентные выражения.
• Простейший пример косвенной рекурсии — про бабочку и китайского философа Чжуан Цзы. Философ спит, и ему снится, что он бабочка, которая спит и ей снится, что она философ, который спит и ему снится, что он бабочка, которая спит и ей снится… Аналогичный пример присутствует у Кэрролла в «Алисе в Зазеркалье»: Алиса спит и видит во сне Чёрного Короля, который спит и видит во сне Алису, которая спит и видит Короля…
• Радиолюбители знают, что принцип рекурсии лежит в основе таких устройств, как мультивибратор и триггер.
• Во многих видеоиграх на принципе рекурсии основаны пасхалки, в которых упоминается название данной игры в контексте игровой же вселенной.
• Всем похуй, что всем похуй.
• Парадокс Рассела (того самого, известного своим чайником): содержит ли себя в качестве элемента множество всех множеств, которые не содержат себя в качестве элемента? Решение парадокса
• Рекурсией часто пользуется Капитан Очевидность.
• Ложные пробуждения (человек просыпается, делает какие-то обычные действия, пребывая в уверенности, что это реальность, а затем просыпается снова — в этот раз, как правило, по-настоящему. Некоторые «просыпаются» и по три раза, и даже больше, такой вот ночной кошмар)
• Фобофобия — страх возникновения фобии. Носители могут бояться смотреть любые фильмы/читать книги/выходить гулять, так как боятся начать шарахаться от… они и сами еще не знают, что станет поводом для их причины похода к психиатру, такой вот Лавкрафт-стайл.
• Награжденный орденом Октябрьской революции крейсер «Аврора» изображён на ордене Октябрьской революции.
• Язык амазонских индейцев пирахан отличается невозможностью построения смысловой рекурсии в предложениях, а также очень малым количеством фонем, отсутствием числительных, грамматического числа и возможности говорить о чём-либо, кроме того, что происходит здесь и сейчас. Что, сцуко, характерно, самоназвание индейцев переводится как «прямоголовые» (в отличие от остальных «кривоголовых» племён).

Галерея рекурсий

• 

  Рекурсивная рекурсия на Гугле.

• 

  Рекурсия IRL.

• 

  Ещё один пример рекурсии.

• 

  И на уютненьком тоже.

• 

  Кистью Магритта

• 

  Гуглорекурсия #2 (смотрим первые пункты в списке суджестов).

• 

  Рекурсия на АИБ.

• 

  Ещё когда фотошопов не было.

• 

  Рекурсия в искусстве: Мауриц Эшер.

• 

  Рисунок в рисунке Эшера

• 

  Вложенный в кота кот.

• 

  Рекурсивный спейсмарин.

• 

  Сёнэн Джамп поясняет.

• 

  Пример от Фортрана.

• 

  Кот, вложенный в монитор.

• 

  Самая опасная ловушка для человека

• 

  Рекурсия и сиськи

• 

  Иван Грозный тоже в теме

• 
• 

  Стас Давыдов

• 
• 
• 
• 
• 

  — Гитлер не был таким уж злодеем: в конце концов, он убил Гитлера.
  — Да, но он также убил парня, что убил Гитлера.
  Далее в тред врывается Капитан.

• 
• 

  Смысл философии

См. также

• Сепульки
• Деление на ноль
• TIME PARADOX
• Уловка-22
• Yo dawg
• Мауриц Эшер
• Хвостовая рекурсия
• Бесконечность

Ссылки

Угощение рекурсией

• Когда ищете в Гугле «рекурсия», убедитесь, что вы не перепутали её с рекурсией.
• Неправильная цитата про рекурсию на башорге
• Правильная цитата про рекурсию на правильном башорге.
• Еще одна, на русском башорге.
• В этом вашем контактике — обратите внимание на «команду».
• Пример рекурсии от Мицгола — «Я не собираюсь отвечать на вопрос анонимного участника о том, почему я не собираюсь отвечать на вопросы анонимных участников. Моё решение рекурсивно». (математически правильнее будет «рекуррентно»).
• Пример рекурсии от анимешницы — «Косплей — это когда по какому-нибудь аниме делают косплей.»
• В иракского ботинкометателя метнули ботинок
• Две трети членов Госдумы прогуляли заседание, посвященное депутатам-прогульщикам
• Уфимский эвакуаторщик эвакуировал эвакуатор
• z0r
• И ядущий станет ядомым
• Песня, удивительно описывающая саму себя и всё что с ней связано (включая будущее после своего написания!!): [1]