Рекурсия

Материал из Википедии — свободной энциклопедии

Реку́рсия — метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса.

Другими словами, рекурсия — частичное определение объекта через себя, определение объекта с использованием ранее определённых. Рекурсия используется, когда можно выделить самоподобие задачи.

Определение в логике, использующее рекурсию, называется индуктивным (см., например, Натуральное число).

[править] Примеры

Алгоритм Жордана-Гаусса для решения СЛАУ является рекурсивным.
Факториал целого неотрицательного числа n обозначается n! и определяется как

n!=n×(n-1)! при n>0 и n!=1 при n=0
Числа Фибоначчи определяются с помощью рекурсии:

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

Для n>2, n-е число Фибоначчи равно сумме (n-1)-го и (n-2)-го чисел Фибоначчи
Практически все геометрические фракталы задаются в форме бесконечной рекурсии. (например, треугольник Серпиньского).
Задача «Ханойские башни». Её содержательная постановка такова:

В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты кольца разных размеров. В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие - кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.

Рекурсивный вариант решения задачи :

Нужно применить рекурсивно алгоритм, переложив n-1 кольцо с первой пирамиды на третью пирамиду. Затем сделать очевидный ход, переложив последнее самое большое кольцо с первой пирамиды на вторую. Затем снова применить рекурсию, переложив n-1 кольцо с третьей пирамиды на вторую пирамиду.

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

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

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

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

Следует избегать избыточной глубины рекурсии, так как это может вызвать переполнение стека вызовов.

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

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

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

[править] Цитаты

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

[править] Юмор

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

рекурсия

см. рекурсия

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

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

Русская народная сказка-песня «У попа была собака…» являет пример рекурсии:

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

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

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

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

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

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

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

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

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

…