Рекурсия

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

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

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

Примеры

• Алгоритм Жордана-Гаусса для решения СЛАУ является рекурсивным.
• Факториал целого неотрицательного числа 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 кольцо с третьей пирамиды на вторую пирамиду.

В языке программирования ActionScript рекурсия выглядит следующим образом:

f_find=function(fName, fPath){            	    // var function
     zz++      // counter+=1
     for (i in fPath) {                        // for in
           if (fPath[i]._name==fName) {        // if condition is true
                 f_N= fPath[i]                 // result
                 return f_N                    // return result to parent function
                 } else {
                       f_find(fName, fPath[i]) // continue Recursion 
                 }
           }
     return f_N                                // return result
};

В данном примере показан в виде рекурсионной функции поиск объекта с конкретно описанными свойствами (в строке 4) внутри бесконечно глубокого дерева объектов.

Или вот так:

function go(n, level) {
     trace(level);
     xlevel = level;
     zz++;
     if (n == 0) {
           return;
     }
     for (var i = 0; i<5; i++) {
           go(n-1,level+1);
     }
}
zz = 0;
go(5,1);
trace(zz+" "+xlevel);

Рекурсия в программировании

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

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

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

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

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

Рекурсия в физике

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

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

Цитаты

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

Юмор

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

; рекурсия : см. рекурсия

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

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

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

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

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

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

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

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

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

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

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

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

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

…

См. также

• Индукция
• Корекурсия