Определения.
Прямая рекурсия - непосредственный вызов алгоритма (функции, процедуры) F из текста самого алгоритма F.
Косвенная (взаимная) рекурсия - циклическая последовательность вызовов нескольких алгоритмов F1, F2, …, Fk (функций, процедур) друг друга: F1 вызывает F2, F2 вызывает F3, …, Fk вызывает F1 (k>1).
Линейная рекурсия - тип рекурсии, при которой рекурсивные вызовы на любом рекурсивном срезе, инициируют не более одного последующего рекурсивного вызова.
Каскадная (древовидная) рекурсия - при каскадной рекурсии, рекурсивные обращения, как правило, приводят к необходимости многократно решать одни и те же подзадачи. И поэтому, по возможности, от неё или следует избавляться или предпринимать шаги, освобождающие от необходимости производить повторные решения подзадач.
Возвратная рекурсия - рекурсивная реализация метода перебора с возвратом (backtracking).
Рекурсивный стек - область памяти, в которую заносятся значения всех локальных переменных алгоритма (программы) в момент рекурсивного обращения. Каждое такое обращение формирует один слой данных стека. При завершении вычислений по конкретному обращению из стека считывается соответствующий ему слой данных, и локальные переменные восстанавливаются, снова принимая значения, которые они имели в момент обращения.
Глубина рекурсии – максимальное число рекурсивных вызовов процедуры без возвратов, которое происходит во время выполнения программы.
Текущий уровень рекурсии – число рекурсивных вызовов в каждый конкретный момент времени.
Рекурсивный спуск – движение вычислительного процесса в направлении последовательных рекурсивных вызовов.
Рекурсивный подъем – движение вычислительного процесса в направлении возврата из ранее вызванных копий рекурсивной процедуры.
2.2. Формы рекурсивных процедур.
Теоретически, рекурсия может быть бесконечной. Однако такой вариант вряд ли кого-нибудь устроит: рекурсивный алгоритм, как и любой нерекурсивный его собрат, обязан выдавать результат своей работы за некое обозримое время. Кроме того, память у компьютера не безгранична, в ней может поместиться лишь конечное число контекстов одновременно открытых экземпляров рекурсивной процедуры. Следовательно, главное требование к рекурсивным процедурам заключается в том, что вызов рекурсивной процедуры должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным. Если условие истинно, то рекурсивный спуск продолжается. Когда оно становится ложным, то спуск заканчивается и начинается поочередный рекурсивный возврат из всех вызванных на данный момент копий рекурсивной процедуры. Признак конца рекурсии может быть как явным (например, в случае реализации факториала), так и неявным.
В общем случае любая рекурсивная процедура P включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова Р и условие В. Структура рекурсивной процедуры может принимать три разные формы:
1. Форма с выполнением действий на рекурсивном спуске:
Procedure P;
Begin
S;
If B Then P;
End;
Пример. Вычислить сумму элементов в массиве A[1..n] целых чисел.
Function Sum ( i, s :Integer ): Integer;
Begin
s := s + a [ i ]; { вычисления на рекурсивном спуске}
If i=n Then Sum:=s
Else Sum:=Sum ( i+1, s ); {рекурсивный спуск}
End;
Вызов: ….. Writeln( Sum ( 1, 0) ); …….
Пример. Рекурсивный вариант создания списка.
Function ListR ( k :Integer) :u;
Var t :u;
Begin
If k=0 Then ListR:=Nil {ссылочное поле последнего узла есть Nil }
Else Begin {создание очередного узла}
New(t); {создали новый}
t^.i := Read ( f, t^.i ); { узел и }
t^.L := ListR (k - 1); подсоединили его к следующему}
ListR:=t;
End;
End;
Вызов: ….. h:=ListR(FileSize(f)); …..
2. Форма с выполнением действий на рекурсивном подъеме:
Procedure P;
Begin
If B Then P;
S;
End;
Пример. Найти минимальный элемент в массиве (1 вариант).
Function Fmin (i :Integer):Integer;
Var min :Integer;
Begin
If i=1
Then Fmin:=a[1]
Else Begin
min:=Fmin(i -1); {рекурсивный спуск}
If a[i]<b Then Fmin:=a[i] { вычисления на рекурсивном подъеме}
Else Fmin:=min;
End;
End;