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

 

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

Прямая рекурсия заключается в том, что подпрограмма в своем блоке использует саму себя.

Пример

Program A;

Procedure B;

Begin

Writeln(‘Пример’);

B;

End;

Begin

B;

End.

Здесь программа А содержит процедуру В, которая будет вызывать сама себя и печатать слово «Пример» бесконечное число раз.

Классическим примером использования рекурсии является вычисление факториала целого положительного числа [5]. Проиллюстрируем на программе.

 

Program DemoRecurs;

Var N:integer;

Function Fact(A:integer):integer;

Begin

If A=0 Then Fact:=1 Else Fact:=A*Fact(A-1);

End;

Begin

While True do

Begin

Writeln('Введите число N');

Readln(N);

Case N of

0: Writeln('0! = 0');

1..9: Writeln(N,'!=',Fact(N));

10: Halt

Else Writeln('Число должно быть в диапазоне 0..9');

End;

End;

End.

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

Часто встречается и другой вариант рекурсии, когда первая подпрограмма вызывает вторую, которая в момент вызова еще не определена. Такая ситуация называется косвенной рекурсией. Для реализации косвенной рекурсии используется так называемое предварительное описание процедур и функций.