Рекурсия

Рекурсивное изображение экрана

Визуальная форма рекурсии страницы Википедии

Визуальная форма рекурсии (эффект Дросте)

The Infinite Cat Project - демонстрация рекурсии с не полным самоподобием на различных кошках

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

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

Использующее рекурсию определение называется индуктивным. Одним из примеров подобного определения является аксиоматическое построение множества натуральных чисел.

Примеры

Треугольник Серпинского

• Метод Гаусса — Жордана для решения систем линейных алгебраических уравнений является рекурсивным.
• Факториал целого неотрицательного числа n (обозначается $n!$) определяется как

  $n!=n\cdot(n-1)!$ при $n>0$ и $n!=1$ при $n=0$

• Числа Фибоначчи определяются с помощью рекуррентного соотношения:

  Первое и второе числа Фибоначчи равны 1

  Для $n>2$, $n-e$ число Фибоначчи равно сумме $(n-1)$-го и $(n-2)$-го чисел Фибоначчи

• Практически все геометрические фракталы задаются в форме бесконечной рекурсии (например, треугольник Серпинского).
• Рекурсивные акронимы: GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor) и т. д.

Рекурсия в программировании

Функции

Блок схема рекурсивного алгоритма решения Ханойской башни.

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция $A$ вызывает функцию $B$, а функция $B$ — функцию $A$. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

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

Впрочем, имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.

Любую рекурсивную функцию можно заменить циклом и стеком.

• См. также примеры реализации функции факториал

Данные

Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов. Пример описания списка (C++):

 struct element_of_list
 {
   element_of_list *next; /* ссылка на следующий элемент того же типа */
   int data; /* некие данные */
 };

Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.

Рекурсия в физике

Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала: в них образуются два коридора из затухающих отражений зеркал.

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

Рекурсия в лингвистике

Способность языка порождать вложенные предложения и конструкции. Базовое предложение кошка съела мышь может быть за счет рекурсии расширено как Ваня догадался, что кошка съела мышь, далее как Катя знает, что Ваня догадался, что кошка съела мышь и так далее. Рекурсия считается одной из лингвистических универсалий, то есть свойственна любому естественному языку (хотя в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии — пираха, которое отмечает лингвист Д. Эверетт). О рекурсии в лингвистике, ее разновидностях и наиболее характерных проявлениях в русском языке описано в статье Е. А. Лодатко «Рекурсивные лингвистические структуры» (см.: Рекурсивные лингвистические структуры)

Цитаты

Итерация от человека. Рекурсия — от Бога. — Л. Питер Дойч

В культуре

Большая часть всех шуток о рекурсии касается бесконечной рекурсии, в которой нет условия выхода. Известные высказывания: 'Чтобы понять рекурсию, нужно сначала понять рекурсию', 'Чтобы что-то сделать, надо что-то сделать' и т. д.

• Весьма популярна шутка о рекурсии, напоминающая словарную статью:

рекурсия 

см. рекурсия

• Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:
  • Рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого», в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки»:

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

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

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

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

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

"У попа была собака, он её любил,

Она съела кусок мяса, он её убил,

В землю закопал,

Надпись написал:

…

См. также

• Индукция
• Математическая индукция
• Корекурсия
• Рекуррентная формула
• Возвратная последовательность
• Докучная сказка
• Обратная связь
• Рефлексивное отношение
• Порочный круг

Ссылки

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.