Рекурсия
Рекурсия (от лат. recurrere — «возвращаться») — неоднозначно трактуемый термин:
- самоповтор;
- включение некоторого объекта или процесса внутрь себя, как части;
- метод синтеза понятий через самоотсылку;
- частный, строгий вариант самоподобия.
Источник парадоксов и бесконечностей: при попытке «пройти» через некоторый рекурсивный объект, находишь в нём самого себя, снова проходишь него, и так по кругу: например, установив два зеркала лицами навстречу, глядя со стороны одного в сторону другого, видишь там отражение, попеременно, то другого зеркала, то этого в другом…
В математике[править]
В мире формальных объектов логики и математики рекурсия объектов порождается самоотсылкой их определений: например, натуральное число есть единица или сумма натуральных чисел.
Множество может включать различные атомарные элементы и/или другие множества. Элементы чистых множеств — это либо ничего (в случае ∅), либо другие чистые множества.
Факториал целого неотрицательного числа n обозначается и определяется как при
Рекуррентные последовательности — это те, в которых значение некоторого (n-го) элемента получается через преобразование других (более базовых). Классический пример — последовательность Фибоначчи: первые два элемента равны 1, каждый последующий — сумма двух предыдущих.
Золотое сечение φ = 1 + 1/φ и, например,
Алгоритм Жордана-Гаусса для решения систем линейных алгебраических уравнений является рекурсивным.
В теории алгоритмов рекурсивное или разрешимое множество — это множество натуральных чисел, не обязательно конечное, принадлежность к которому любого данного натурального числа́ можно установить за конечное время через выполнение известного алгоритма.
Виды рекурсии[править]
- рекурсивная формула;
- рекурсивная функция;
- рекурсивная последовательность;
- рекурсивный алгоритм;
- рекурсивная программа;
- рекурсивное изображение.
Компьютерное программирование[править]
Программирование компьютеров задействует рекурсию многими различными способами. На одном плане, рекурсия бывает либо у вычислений (процедура, подрутина, процесс), либо же у данных (структура данных, тип данных). На другом плане, следует различать рекурсию на уровне кода от рекурсии «самих по себе» процессов или данных: рекурсивные типы данных могут видоизменяться на стадии компиляции — в нерекурсивные; рекурсивные функции — исполняться итеративно; в теории, возможно и обратное.
Рекурсия у функций[править]
В программировании рекурсия — вызов функции (процедуры) из неё же самой непосредственно (простая рекурсия) или же будучи вызванной «назад» через другие функции. Пример взаимной рекурсии: функция А вызывает функцию 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.
Ссылки[править]
- Схема примитивной рекурсии
- Рекурсия в энциклопедии «Викиреальность»