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

Обычно, в программировании под рекурсией понимают такую реализацию, в которой подпрограмма использует в своем теле вызов самой себя. Такие вызовы называют рекурсивными. Когда функция A в своем теле вызывает только одну рекурсивную функцию (саму себя), то говорят о простой рекурсии. Под косвенной рекурсией понимают явление, когда рекурсивные функции вызывают друг друга (например, функция А вызывает B, а функция B вызывает A).

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

Факториал

Для рекурсивного решения задачи обычно мы стараемся решить задачу через саму себя (как это ни странно), но с меньшими параметрами. Например, самым простым примером рекурсивного решения служит задача о вычислении факториала. Конечно, факториал можно вычислить и без рекурсии, но рекурсивное решение выглядит изящнее. Здесь нужно определить некоторую функцию F(n), которая будет вычислять значение n! через саму себя. В данном случае воспользуемся рекуррентной формулой: F(n) = F(n-1)*n. Учтем и условие выхода: если n меньше 2, то ответ равен 1. Таким образом, в тех случаях, когда n меньше 2х, функция не будет себя вызывать, что будет гарантировать выход из рекурсии. Описанные выше рассуждения преобразуем в следующую запись:

Числа Фибоначчи

Аналогично определим функцию для вычисления элементов ряда чисел Фибоначчи, исходя из рекуррентного выражения F(n) = F(n-1) + F(n-2) :

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

Задача о Ханойской башне

A	B	C

Задача: Имеется три стержня, на один из которых нанизаны N колец, причем кольца отличаются размером и лежат меньшее на большем. Требуется перенести пирамиду из N колец с одного стержня на другой за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

Предположим, что мы хотим получить в итоге программу, которая по заданному значению N будет нам выводить последовательность действий, решающих задачу, т.е. алгоритм переноса всех колец со стержня А на стержень B. Действие переноса одного кольца будет иметь вид: A -> B, что означает перенос одного верхнего кольца со стержня с именем А, на стержень с именем B. Рассмотрим, как должны выглядеть решения для малых N:

N=1: A -> B
N=2: A -> C, A -> B, C -> B
N=3: A -> B, A -> C, B -> C, A -> B, C -> A, C -> B, A -> B

Решение: Для человека, не знакомого с рекурсией, задача кажется очень сложной. На самом деле поставленная задача о переносе N колец с одного стержня на другой с использованием 3-го стержня как вспомогательного легко выражается через 2 подобных задачи для N-1 кольца и оптимальным решением поставленной задачи для N колец будет алгоритм, реализующий это за 2^N-1 действий. Рассмотрим, как умея перекладывать N-1 кольцо возможно переложить N колец. Для этого необходимо выполнить следующие 3 действия:

1. переложить N-1 кольцо с исходного на временный стержень
2. переложить 1 кольцо с исходного на конечный стержень
3. переложить N-1 кольцо с временного на конечный стержень

Заметим, что 0 и 1 кольцо мы умеем перекладывать. Для лучшего понимания следует сказать, что N-1 кольцо будет перекладываться через 2 действия с N-2 кольцами, N-2 кольца через 2 действия с N-3 кольцами и т.д. пока не опустимся до нуля. Отметим так же, что при переложении N-1 кольца, N-е (и кольца еще большего диаметра) никак не мешают. Опишем теперь эту рекуррентную запись в виде функции:

Теперь для того, чтобы получить решение задачи для N=8 достаточно вызвать вышеописанную функцию, например, следующим образом: