Автор Игр
академик

ЭКСПОНАТ

№ 011424
22
50021

Рекурсия

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

(Залогиньтесь, чтобы почистить страницу.)

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

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

Треугольник Серпинского — фрактал, один из двумерных аналогов множества Кантора предложенный польским математиком Серпинским в 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 — настольная ролевая игра.


Пакмэн



Ычан




Тэги:литература, логика, методика, программирование, рекурсия
Опубликовал:академик Автор Игр 15 апреля 2011

Рейтинг экспоната:

ОБСУЖДЕНИЕ ЭКСПОНАТА


академик kot-obormot 15 апреля 2011 17:21
А где классика жанра - зеркальный коридор????

8


академик Kenny Zhyv 15 апреля 2011 17:30
Да, рекурсия штука завораживающая. Кстати, она часто использовалась в рекламе. В советское время были чипсы московские, где на упаковке была изображена девочка с пакетом чипсов. Тех же самых, которые она держала в руке. А на пакете нарисованных чипсов была такая же девочка. В детстве эта упаковка буквально разрывала мне моск.

14


профессор Obean 15 апреля 2011 17:51
Непонял про таверну, а так отличненькая статья, заняла меня на время раза в 3 более чем даже сегодняшняя подборка демов

5


профессор Obean 15 апреля 2011 17:53
О а мне рвало моцк бутылка воды, где сидел мальчик рядом с бутлем, на котором был нарисован он же сидящий рядом с бутлем, на котором был нарисован он сидящий рядом с бутлем на котором был нарисован он сидящий рядом с бутлем, на котором был нарисован он сидящий.....

5


академик VAdim 15 апреля 2011 19:26
Рекурсия - одна из немногих математических фиговин, которая, мало того что широко распространилась за пределами математики и математиков, но еще и может претендовать на понимание со стороны абсолютных нематиматиков!)

12


академик Triton7742 15 апреля 2011 20:57
Obean, соль стрипа про таверну заключается в том, что игроки в D&D, в которую играют с использованием кубиков, листов персонажей и прочего, в самой игре пытаются сыграть в D&D, в которую играют с использованием кубиков, листов персонажей и пр.

5


академик valerie 15 апреля 2011 21:08
Является ли Algorithm March http://youtu.be/CUSUwv71TOw рекурсией?

3


профессор d7 15 апреля 2011 21:45
Еще мульт советский был.

4


профессор aviakot 15 апреля 2011 23:37
Рекурсивный кот доставил!

7


профессор qDan 16 апреля 2011 02:14
Рекурсия - штука интересная, но, неподготовленный неофит, плохо знакомый с сутью рекурсии, может легко скукожить свой моск в считанные минуты.

Кстати, был неплохой фильм-пародия на Звёздные Войны (Space Balls или, Эпизод 0: Космояйца), в котором глав. злодеи, дабы выследить сбежавших глав. героев, воспользовались кассетой с уже отснятым фильмом, чем совершили нехилый рекурсивный ряд, а заодно создали небольшой временной парадокс.

5


академик Дядя Вонь 16 апреля 2011 02:23
Как человек, безнадежно испорченным чтением классики, скажу, что они эту идею потырили у Сервантеса. Во втором томе Дон Кихот держит в руках первый том о собственных похождениях.

7


профессор Forever alone 16 апреля 2011 14:28
добавлю в избранное, детям показывать, когда время придет=)
А так очень люблю шутки про рекурсию, затягивают) а тут такая шикарная подборка)

4


академик valerie 16 апреля 2011 17:04
Дядя Вонь, не вижу ни парадокса, ни рекурсии в том, что герой во ВТОРОМ томе читает ПЕРВЫЙ том описания собственных похождений. Впрочем, я не специалист.

6


академик Дядя Вонь 16 апреля 2011 17:49
(делая снобическую мину) Ну, мы с Борхесом никому не навязываем своего мнения.

3


профессор Плюсатор 16 апреля 2011 21:26
Минусам нет!

5


академик kot-obormot 17 апреля 2011 13:41
Кстати, ещё "купи слона" забыли упомянуть. ИМХО, более распространённый вариант, чем ветхозаветный белый бычёк.

6


аспирант KriChi 17 апреля 2011 16:49
Лучше всего эту тему раскрывает фильм - Фракталы http://www.youtube.com/watch?v=Yke32Oavr1I

2


профессор eletau 17 апреля 2011 21:16
Я в это просто не верю. Никто еще до сих пор не пошутил про трифорс Серпинского?..

2


доцент janne 19 апреля 2011 18:14
интересная статейка. увлекла

1


академик gagin 20 апреля 2011 03:19

2


аспирант ХомяГг 23 апреля 2011 13:56
Рекурсия-крутая штука...
рЭкурсиОЙ рулЫт!!!

0


профессор holyman 18 мая 2011 13:44
Еще можно посмотреть на рекурсию, если подключить камеру к телевизору и снимать телевизор. И в журнале "Мурзилка" вроде бы был на обложке маскот с журналом "Мурзилка" на котором...

1

Только зарегистрированные и авторизованные пользователи могут оставлять комментариии.

ПРОПУСК НИИ МЕДВЕД

имя

пароль

войти

Загрузка...