Рекурсия

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

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

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

Содержание

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

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

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

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

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

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

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

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

Лекция 4: Рекурсия // НОУ ИНТУИТ [1:45:05]

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

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

[править] Рекурсия в программировании

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

[править] Функции

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

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

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты