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

3. Рекурсивные подпрограммы
В теле подпрограммы доступны все объекты, описанные в программе, в том числе и имя самой подпрограммы. Процедуры и функции, использующие вызовы самих себя, называют рекурсивными (прямая рекурсия).
Рекурсия – это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе.
Типичная рекурсивная процедура имеет вид:
procedure Rec (n:Integer);
begin
<действие на входе рекурсию>
if <проверка условия> then Rec(n-1);
<действия на выходе из рекурсии>;
end;
Рассмотрим пример рекурсивной функции вычисления хⁿ, где x – целое число, а n – целое неотрицательное число.
Воспользуемся известным фактом:

function Deg(x, n: integer):longint;
begin
if n = 0 then Deg:=1
else Deg:=Deg(x, n-1)*x;
end;
На рис. 1 показаны прямой и обратный ход рекурсии. Обратите внимание, что в любой рекурсивной подпрограмме обязательно должна быть нерекурсивная ветвь, в нашем случае – это if n = 0 then Deg:=1
При выполнении рекурсивных подпрограмм используется специальная область памяти, называемая «стеком возвратов». В нем запоминаются адреса точек возврата и значения локальных переменных.
Пусть переменной a присваивается значение 2⁴:

Рисунок 1 - Прямой и обратный ход рекурсии
Не следует путать рекурсию с итерацией – повторяемым выполнением некоторых действий до тех пор, пока не будет удовлетворяться некоторое условие. Хотя использование рекурсивной формы организации алгоритма обычно выглядит изящнее итерационной и дает более компактный текст программы, следует помнить, что при рекурсивном программировании велика вероятность ошибок, способных вынудить программиста к выполнению перезагрузки компьютера. Кроме того, если глубина рекурсии очень велика, то оттранслированная программа будет требовать во время выполнения много памяти, что может привести к переполнению стека.
В начале каждой рекурсивной процедуры или функции можно поместить строку if KeyPressed then Halt;, позволяющую при «зависании» программы выйти из нее без перезагрузки компьютера, простым нажатием любой клавиши. Функция KeyPressed возвращает результат true, если на клавиатуре была нажата клавиша, порождающая символ, и false – в противном случае. Например, оператор repeat until KeyPressed; содержит пустой оператор и обеспечивает паузу при выполнении программы до нажатия клавиши.