Рекурсия

Обложка альбома Ummagumma банды Pink Floyd.

Что такое рекурсия. самое простое объяснение // 3 минуты [2:15]

Рекурсия (от лат. recurrere — «возвращаться») — самоповтор: включение некоторого объекта или процесса внутрь себя, как части. Метод синтеза понятий через самоотсылку и частный, строгий вариант самоподобия.

Источник парадоксов и бесконечностей: при попытке «пройти» через некоторый рекурсивный объект, находишь в нём самого себя, снова проходишь него, и так по кругу: например, установив два зеркала лицами навстречу, глядя со стороны одного в сторону другого, видишь там отражение, попеременно, то другого зеркала, то этого в другом…

В математике

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

Множество может включать различные атомарные элементы и/или другие множества. Элементы чистых множеств — это либо ничего (в случае ∅), либо другие чистые множества.

Факториал целого неотрицательного числа n обозначается $n!$ и определяется как $n!=n\times (n-1)!$ при $0!=1$

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

Золотое сечение φ = 1 + 1/φ и, например, $\varphi ={\sqrt {1+{\sqrt {1+{\sqrt {1+{\sqrt {1+\cdots }}}}}}}}.$

Алгоритм Жордана-Гаусса для решения систем линейных алгебраических уравнений является рекурсивным.

В теории алгоритмов рекурсивное или разрешимое множество — это множество натуральных чисел, не обязательно конечное, принадлежность к которому любого данного натурального числа́ можно установить за конечное время через выполнение известного алгоритма.

Виды рекурсии

• рекурсивная формула;
• рекурсивная функция;
• рекурсивная последовательность;
• рекурсивный алгоритм;
• рекурсивная программа;
• рекурсивное изображение.

Компьютерное программирование

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

Рекурсия у функций

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

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

Хвостовая рекурсия

Хвостовая рекурсия — это самовызов функции в последнюю очередь, без дальнейших вычислений, кроме возврата — в предыдущий уровень подвызова функции, либо в среду.

Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), выполняют хвостовую рекурсию в ограниченном объёме памяти при помощи итераций: "зацикленность" программной структуры выслеживается на стадии компиляции, и при работе программы не потребуются ресурсы для выделения памяти отдельно для каждого уровня рекурсивной вложенности.

Рекурсивные определения типов данных

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

class element_of_list; /* необходимо по правилам C++ */
class element_of_list
{
  element_of_list *next; /* ссылка на следующий элемент того же типа */
  int data; /* некие данные */
};

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

Культура

В гуманитарных областях особые рекурсивные явления называются эффект Дросте и Mise en abyme (мизинаби́м.)

Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:

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

Юмор

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

Распространено остроумное «энциклопедическое определение» рекурсии через самодемонстрацию: «Рекурсия: см. рекурсия.»

Другие алгоритмы

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

Литература

• Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4.
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.

Ссылки

• Схема примитивной рекурсии
• Рекурсия в энциклопедии «Викиреальность»