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

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

Классический пример использования рекурсии – вычисление факториала целого положительного числа.

Program Demorec;

Var N: Integer;

Function Fact (k:Integer):Integer;

Begin

If k=0 then Fact:=1

else Fact:=k*Fact(k-1);

End;

Begin

Write ('Введите число ->'); Readln (N);

Writeln ('N!=',Fact(N));

End.

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

Предварительное описание подпрограмм

Для реализации алгоритмов с косвенной рекурсией в языке Паскаль предусмотрена специальная директива предварительного описания подпрограмм Forward.

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

Program DF;

Procedure P2 (формальные параметры); Forward;

Procedure P1;

Begin

P2(фактические параметры);

End;

Procedure P2; {список формальных параметров не повторяется}

Begin

P1;

End;

Begin {основная программа}

P1

End.