Лекция: Программирование с использованием рекурсии

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

Function Factorial (N: Integer): Integer;

Begin if N = 1 Then Factorial := 1 Else Factorial := N*Factorial(N -1) End;

Ниже приведена рекурсивная функция, предназначенная для вычисления наибольшего общего делителя двух целых чисел N1 и N2.

ПримерFunction HighFactor(N1 ,N2:lnteger):lnteger;

Var P: Integer; Begin lf N1 > N2 Then P:=HighFactor(N1,N2) Else

If N2<=0 Then p:= N1 {нерекурсивное решение}

Else P:=HighFactor(N2,N1 Mod N2); HighFactor := P End;

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

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

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