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

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

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

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

n!=n*(n-1)!,

а факториал числа 1 равен 1.

Var

x,fact:integer;

Function Factorial(n:integer):integer;

Begin

if (n=1) then

Result:=1

Else

Result:=n*Factorial(n-1);

end;

Begin

write(’Введите число n:’); readln(x);

fact:=Factorial(x);

write(’n!=’, fact);

End.

Расчет факториала в рассмотренном примере схематически представлен на рис. 3.9.

n!= n * (n-1)!

(n-1)*(n-2)!

(n-2)*(n-3)!

......

(n-(n-3))*2!

2*1!

=1

Рис. 3.9. Схема расчета факториала с помощью рекурсии

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