Рекурсия
Функция называется рекурсивной, если во время ее обработки возникает ее повторный вызов,
либо непосредственно, либо косвенно, путем цепочки вызовов других функций.
Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции.
int a()
{.....a().....}
Косвенной рекурсией является рекурсия, осуществляющая рекурсивный вызов функции
посредством цепочки вызова других функций. Все функции, входящие в цепочку, тоже
считаются рекурсивными.
Например:
a(){.....b().....}
b(){.....c().....}
c(){.....a().....} .
Все функции a,b,c являются рекурсивными, так как при вызове одной из них, осуществляется
вызов других и самой себя.
Рассмотрим задачу о Ханойских башнях. Имеются три стержня с номерами 1,2,3. На стержень
1 надето n дисков различного диаметра так, что они образуют пирамиду (см.рис.32).
Написать программу для печати последовательности перемещений дисков со стержня на
стержень, необходимых для переноса пирамиды со стержня 1 на стержень 3 при использовании
стержня 2 в качестве вспомогательного. При этом за одно перемещение должен переноситься
только один диск, и диск большего диаметра не должен помещаться на диск меньшего диаметра.
Доказано, что для n дисков минимальное число необходимых перемещений равно 2^n-1.
Рис.31. Задача о Ханойских башнях.
Для решения простейшего случая задачи, когда пирамида состоит только из одного диска,
необходимо выполнить одно действие - перенести диск со стержня i на стержень j, что
очевидно (этот перенос обозначается i -> j). Общий случай задачи изображен на рисунке,
когда требуется перенести n дисков со стержня i на стержень j, считая стержень w
вспомогательным. Сначала следует перенести n-1 диск со стержня i на стержень w при
вспомогательном стержне j, затем перенести один диск со стержня i на стержень j и,
наконец, перенести n-1 диск из w на стержень j, используя вспомогательный стержень i.
Итак, задача о переносе n дисков сводится к двум задачам о переносе n-1 диска и одной
простейшей задаче. Схематически это можно записать так: T(n,i,j,w) = T(n-1,i,w,j),
T(1,i,j,w), T(n-1,w,j,i).
i n-1 w n-1 j
+ | -------->-+|+--------->+ |
n-1| | I ||| Ш | |
+ / \ / \ / \
+-/-----\-+ / \ +-/-----\-+
==+----|----+===/=========\====+----|----+======
+-------------->-------------+
П
Рис.33. Схема решения задачи о Ханойских башнях.
Ниже приведена программа, которая вводит число n и печатает список перемещений, решающая
задачу о Ханойских башнях при количестве дисков n. Используется внутренняя рекурсивная
процедура tn(n,i,j,w), печатающая перемещения, необходимые для переноса n дисков со
стержня i на стержень j с использованием вспомогательного стержня w при
{i,j,w} = {1,3,2}.
/* ханойские башни */
#include
main() /* вызывающая */
{ void tn(int, int, int, int); /* функция*/
int n;
scanf(" %d",&n);
tn(n,1,2,3);
}
void tn(int n, int i, int j, int w) /* рекурсивная */
{ if (n>1) /* функция */
{ tn (n-1,i,w,j);
tn (1,i,j,w);
tn (n-1,w,j,i);
}
else printf(" \n %d -> %d",i,j);
return ;
}
Последовательность вызовов процедуры tn при m=3 иллюстрируется древовидной структурой на
рис.34. Каждый раз при вызове процедуры tn под параметры n, i, j, w выделяется память и
запоминается место возврата. При возврате из процедуры tn память, выделенная под
параметры n, i, j, w, освобождается и становится доступной память, выделенная под
параметры n, i, j, w предыдущим вызовом, а управление передается в место возврата.
Рис.33. Последовательность вызовов процедуры tn.
Во многих случаях рекурсивные функции можно заменить на эквивалентные нерекурсивные
функции или фрагменты, используя стеки для хранения точек вызова и вспомогательных
переменных.
.