Рекурсия в реальной жизни

Февраль. Ну, привет, февраль. Мы тебе рады. А сегодня и подавно. Потому что 2 февраля это самый цикличный и рекурсивный день в мире благодаря фильму «День Сурка». Рекурсия это когда что-то содержит само себя или описывается через само себя: матрешка внутри матрешки, зеркало напротив зеркала, ветка, повторяющая дерево. В программировании так называют метод, который вызывает сам себя, и, как в «Дне сурка», из рекурсии нужен выход: базовый случай, на котором вызовы останавливаются. Ниже собраны примеры рекурсии из кино, природы, литературы, живописи и программистского фольклора.

Кратко

• Рекурсия это самоподобие: объект или процесс содержит уменьшенную копию самого себя, а та содержит еще одну, и так далее.
• Рекурсия бывает бесконечной (два зеркала друг напротив друга, веб-камера, направленная на монитор) и конечной (матрешка, у которой есть самая маленькая).
• В природе рекурсия выглядит как фрактал: остров в озере на острове в озере, ветки дерева, лист папоротника, капуста романеско, снежинки и дендриты металлов.
• В литературе это «книга в книге», сон во сне и бесконечные сказки вроде «У попа была собака»; в живописи «картина в картине».
• Разница с циклом: цикл повторяет одно и то же действие, а рекурсия вкладывает уровни друг в друга и потом разворачивает их обратно.
• В программировании рекурсия без базового случая заканчивается StackOverflowError; классические задачи на рекурсию: факториал, числа Фибоначчи, Ханойские башни.

В этом цикле зимы можно-таки еще разок посмотреть тот самый «День Сурка» (2.02) и «День Радио» (13.02), поболеть за любимых спортсменов на зимних стартах, поесть блинов на Масленицу, подарить «Валентинку» (14.02) и очередной лосьон для бритья (23.02), поздравить с праздником полярного медведя (27.02)… А там и новый цикл весны наступит.

Рекурсия в кино и в быту

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

Примеры рекурсии в природе

Самым зрелищным примером рекурсии являются географические объекты. Например, похожие на вышеупомянутые матрешки, острова посреди озер, которые в свою очередь расположены на островах. Среди таких объектов самым известным является пресноводное озеро Тааль, расположенное на острове Лусон в провинции Батангас, Филиппины. На озере находится вулканический остров Тааль, в его кратере имеется еще одно озеро. А на нем в свою очередь есть свой собственный небольшой остров, Вулкан-Пойнт. Наглядным примером также являются реки, образованные из других рек, горы и молнии. Не менее интересны примеры «овощных» рекурсий. Вот, к примеру, обычный репчатый лук и белокочанная капуста: Совсем иначе выглядят рекурсии у цветной капусты и капусты романеско. Их головки состоят из соцветий, которые, в свою очередь, состоят из соцветий. Интересно, что головка капусты романеско состоит из соцветий светло-зеленого цвета, которые имеют форму фрактальной спирали. Кроме этого, каждый отдельный бутон образует свою спираль. Дерево состоит из веток. Ветка в свою очередь состоит из более маленьких веточек. Каждая ветка повторяет дерево. Такую же структуру можно наблюдать у сложного листа папоротника: Семена некоторых цветов (например, подсолнечника) расположены пересекающимися спиралевидными веерами, определяемыми соотношением чисел Фибоначчи: Замечательным примером рекурсии являются дендриты, сложнокристаллические образования древовидной ветвящейся структуры. Нам всем знакомы ледяные дендриты, это снежинки и морозные рисунки на стекле: Также встречаются дендриты металлов, например, золота и меди: Примеры рекурсии из животного мира, тоже достаточно наглядны: извечная пара «курица и яйцо» и … эволюция:

Примеры рекурсии в лингвистике и литературе

Рассказ из «Кибериады» Станислава Лема о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей. (бесконечная рекурсия: каждая новая машина строила себе подобную). Н.В. Гоголь в повести «Портрет» описывает сон художника Черткова, который проснувшись снова попадает в сон, проснувшись от этого сна, он попадает в первый сон, от которого тоже придется проснуться. "Мастер и Маргарита" это один из наиболее ярких рекурсивных романов. Тема Иешуа и Пилата рекурсивно вызывается из темы Мастера и Маргариты. Кроме того, здесь также используется прием "книга в книге". Мастер пишет роман об Иешуа и Пилате, текст которого сливается с текстом книги "Мастер и Маргарита". Еще один пример рекурсии: английская народная песенка «Дом, который построил Джек» в переводе Маршака. Или вот, самый короткий рассказ Айзека Азимова, написанный на спор прямо в студии во время записи интервью. Самыми же известными примерами бесконечной рекурсии в литературе являются «бесконечные сказки»: Я открыл свои глаза: Голубые небеса, И зелено покрывало, И мохнатые леса… Вот и речка, все течет, Солнце встало, вновь печет… Взял я ручку и тетрадь И решил все записать, Я открыл свои глаза: Голубые небеса… У попа была собака У попа была собака, Он ее любил, Она съела кусок мяса, Он ее убил И в землю закопал, И памятник поставил, И надпись написал: У попа была собака, Он ее любил, Она съела кусок мяса

Примеры рекурсивной графики

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

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

Это просто жесть. Программисты, епта, живем втроем, договорились так: первый будит второго, второй третьего, третий первого… рекурсия =) в результате проспали лекцию. У нас на обед салат «Рекурсивный»: помидоры, огурцы, салат. xxx: помнишь Антоха желание проиграл? так вот, я ему загадал: чтобы он 2 дня на все предметы, с которыми совершил какие-либо действия клеил стикер с этим действием yyy: я бы точно клеил бы на стикер стикер с надписью «наклеил». Мелкого (сына 10 мес) вогнал в рекурсию… одна соска во рту. дал вторую. первую от радости выплюнул. вставил вторую. услышал как что-то упало. обрадовался увидев первую соску. выронил вторую. засунул первую в рот. услышал как что-то упало… уже 5 минут меняет их. Сегодня работал с отцом, он мне говорит типа «хочешь рекурсию покажу?», я типа «ну давай». Он берет втыкает вилку дрели в удлинитель, а вилку удлинителя втыкает в свободную розетку этого же удлинителя, жмет кнопку, дрель начинает работать… Блин наверное у меня было очень смешное лицо, он ржал до вечера, а я еще долго втыкал почему же так получается. Оказалось дрель была на аккумуляторе. Если же вы считаете, что все в жизни должно иметь прикладное применение, то предлагаем вам вспомнить полученные знания по программированию и попробовать решить некоторые из известных задач, которые решаются с помощью рекурсивных методов: нахождение чисел Фибоначчи и факториала, а также головоломку «Ханойские башни». Февраль. Ну привет, февраль. Мы тебе рады. А сегодня и подавно.

Вопросы и ответы

Что такое рекурсия простыми словами?

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

Чем рекурсия отличается от цикла?

Цикл повторяет одно и то же действие на одном уровне: день сурка внешне выглядит именно как цикл. Рекурсия вкладывает уровни друг в друга: каждый шаг открывает новый, меньший экземпляр той же задачи, а потом результаты собираются в обратном порядке, от самой маленькой матрешки к самой большой. Любую рекурсию можно переписать циклом со стеком, но для деревьев, вложенных структур и задач вроде Ханойских башен рекурсивная запись короче и понятнее.

Почему рекурсию в природе называют фракталами?

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

Что произойдет, если рекурсия в программе бесконечная?

Каждый вызов метода занимает место в стеке вызовов, и без условия выхода стек переполняется: Java бросает StackOverflowError, по документации он возникает, «когда приложение рекурсирует слишком глубоко». В стектрейсе будет один и тот же метод, повторенный тысячи раз. Лекарство одно: базовый случай, при котором метод возвращает ответ без нового вызова, и гарантия, что каждый вызов к нему приближается.

Какие классические задачи решают рекурсией?

Факториал (n! это n, умноженное на (n-1)!), числа Фибоначчи (каждое следующее это сумма двух предыдущих), Ханойские башни (переложить n дисков значит переложить n-1, потом один, потом снова n-1), обход дерева каталогов и файлов, разбор вложенных скобок и JSON, быстрая сортировка и сортировка слиянием. Общий признак: задача естественно разбивается на такие же задачи меньшего размера.

Где рекурсия встречается в языке и литературе?

В самом языке: предложение может содержать придаточное, которое содержит еще одно придаточное, и так без предела. В литературе это «книга в книге», как роман Мастера внутри «Мастера и Маргариты», сон во сне у Гоголя, цепные песенки вроде «Дома, который построил Джек» и бесконечные сказки, которые заканчиваются своим же началом: «У попа была собака…».