Рекурсия

Материал из Lurkmore.

Анонимус! Альтернативное мнение также имеется в смехуечках.

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

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

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

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

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

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

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

IRL же, визуальную рекурсию можно легко получить встав между двух стоящих друг напротив друга зеркал. Например, в коридоре вагона поезда.

Примеры

Бесконечный цикл. В рекурсию он превращается только при условии, что звонит чел на автоответчик.

• «Установите драйвера для CD-ROM, находищиеся на нашем компакт-диске».
• «Для выхода в Интернет скачайте из Интернета нашу программу».
• winrar_setup.rar
• «Keyboard not found. Press anykey to continue».

Рекурсия в кино

• В фильме «12 друзей Оушена» представлен интересный пример рекурсии: Джулия Робертс сыграла героиню, которая по сюжету фильма некоторое время играла Джулию Робертс.
• В этом вашем Хаусе в конце втрого сезона Хаус видит галлюцинацию, в которой он в свою очередь тоже видит галлюцинацию. Кто смотрел, поймет.

Простейший пример рекурсии в диалоге

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

• Хаскель состоит из рекурсии чуть менее, чем полностью.
• Scheme же состоит из рекурсии чуть более, чем полностью.
• Реакция на слово «рекурсия» типичного ПеХаПе-программиста.

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

Из инструкции ФАПСИ от 13 июня 2001 года N 152:

В музыке

xkcd о рекурсии

• Известный хит Deep Purple «Smoke On The Water» повествует нам о сгоревшем здании, в котором должен был записываться альбом, на который вошла песня, повествующая…
• Ирландский расовый Bog down in the valley.
• Верный пример рекурсии из этого вашего Сплина:

• Ещё такая детская песенка:

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

В работе

В армии

На кухне

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

— 100219

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

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

• GNU — GNU is not unix
• WINE — WINE is not an emulator
• PINE — PINE is not elm
• LAME — LAME Ain’t a MP3 Encoder
• PHP — PHP Hypertext Preprocessor
• Gajim — Gajim is a jabber instant messenger
• PNG — PNG is Not GIF

Внезапно:

• VISA — Visa International Service Association

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

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

(defun fact(x)
  (if (integerp x)
    (if (= x 0)
      1
      (* x (fact (1- x))))))

Алсо

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

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

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

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

Ссылки

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

• Когда ищете в Гугле «рекурсия», убедитесь, что вы не перепутали её с рекурсией.
• Неправильная цитата про рекурсию на башорге
• Правильная цитата про рекурсию на правильном башорге.
• Самое лаконичное определение рекурсии
• Пример рекурсии от Мицгола — «Я не собираюсь отвечать на вопрос анонимного участника о том, почему я не собираюсь отвечать на вопросы анонимных участников. Моё решение рекурсивно». (математически правильнее будет «рекуррентно»).
• Пример рекурсии от анимешницы — «Косплей — это когда по какому-нибудь аниме делают косплей.»
• Рекурсия от Cyanide and Happiness и ещё
• В иракского ботинкометателя метнули ботинок

См. также

• w:Факториал
• en.w:Lambda calculus
• Сепульки
• Хвостовая рекурсия.

[ + ] Капитан заявляет: «Рекурсия имеет отношение к Башоргу. Так-то!».

[Мета]  Аппрув • Бездна • Вордстрим • Копипаста • Локальные мемы башорга • На башорг [Аппруверы]  DarkRider • Zoi • aalien • Creator • Asuka • jozhig • Биоланте (бывший) [Мемы]  ++i + ++i • BB-код • Businassman • Админ • Блондинка/CAPSLOCK • Вертолет • Если трактористы - женщины • Зеленоград • Извините за неровный почерк • Конина блядская • Котомальчик • Криветко • Минет • Патчить KDE2 под FreeBSD • Пчёлы против мёда • Рекурсия • Шредер • Урановые ломы • Что будет, если в унитаз поезда на полном ходу бросить лом? • Я кончил и закурил • Ящик пива • Ящитаю [Вордстрим]  Влад Чесноков • Вордстримовские войны • Плюсообмен • Проверочка [Бездна]  Накипело • Чувак с долларами

[ + ]  Любой программист без словаря поймёт, что такое Рекурсия

Промышленные  1С • C# • C++ • JavaScript (Ajax) • Pascal • Perl • PHP • Pure C • Python • ABAP • Ассемблер • Васик • Жаба Эзотерические  BrainFuck • Erlang • Forth • Haskell • LISP (My other car) • Prolog • Tcl • TeX Профессии  Быдлокодер • Программист • Тестировщик • Хакер • Хеллоуворлдщик Методы и стили  Reverse Engineering • Выстрелить себе в ногу • Грязный хак • Индусский код • Костыль • Метод научного тыка • Помолясь • Свистелки и перделки Прочее  ++i + ++i • Kiss • Foobar • Regexp • SICP • sql.ru • ЕГГОГ • Лог • %s • Рекурсия • Тест Тьюринга • Умение разбираться в чужом коде • Фаза Луны • Фатальный недостаток

[ + ]   Рекурсия ⊆ Рекурсия

Мета  Бесполезная наука • Высшая математика • Матан • Сопромат Люди и организации  Березовский • Вассерман • Инженер • ИТМО • Кари Байрон • Леонардо да Винчи • Лобачевский • Луговский (Цитатник Луговского) • Миша Вербицкий • Никола Тесла • Перельман • Ричард Докинз • Стивен Хокинг • МФТИ • НМУ • Пятисемиты • Технофашисты Достижения  TeX • Атомная бомба • Биореактор • Большой адронный коллайдер • Большой взрыв • ГМО • Квантовая механика • Корчеватель • Кубик Рубика • Теория относительности • Ту-154 • Чёрная дыра • Чернобыль • Элементарные Частицы Мемы  265 • xkcd • Деление на ноль (Яценюк)• Дигидрогена монооксид • Задача Льва Толстого • Задача Эйнштейна • Кот Шрёдингера • Матановая капча • Метод научного тыка • Поймать льва в пустыне • Рекурсия • Сферический конь в вакууме • Фотон • Число Эрдёша Паранаука  Science freaks/Научное фричество • Алекс Лотов • Британские учёные • Великая тайна воды • Вечный двигатель • Гаряев • ГСМ • Малахов • Мулдашев • Грабовой • Околонаучная хуйня • РАЕН • Соционика • Телепортация • Торсионные поля • Устин Чащихин • Чудинов • Чурляев • Электронный Голосовой Феномен Срачи  Луносрач • Плутоносрач • Наука vs Религия • Физики vs лирики • Взлетит или не взлетит?