Рекурсия

Материал из Циклопедии
Перейти к навигации Перейти к поиску
Обложка альбома Ummagumma банды Pink Floyd.
Что такое рекурсия. самое простое объяснение // 3 минуты [2:15]

Рекурсия (от лат. recurrere — «возвращаться») — неоднозначно трактуемый термин:

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

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

В математике[править]

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

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

Факториал целого неотрицательного числа n обозначается и определяется как при

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

Золотое сечение φ = 1 + 1/φ и, например,

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

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

Виды рекурсии[править]

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

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

Mutual recursion.jpg


Рекурсия у функций[править]

В программировании рекурсия — вызов функции (процедуры) из неё же самой непосредственно (простая рекурсия) или же будучи вызванной «назад» через другие функции. Пример взаимной рекурсии: функция А вызывает функцию 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.

Ссылки[править]