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

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

Приведенная ниже программа содержит функцию Factorial для вычисления факториала. Напомним, что факториал числа определяется через произведение всех натуральных чисел, меньших либо равных данному (факториал числа 0 принимается равным 1):

X! = 1 * 2 * ... * (X – 2) * (X – 1) * X

Из определения следует, что факториал числа X равен факториалу числа (X – 1), умноженному на X. Математическая запись этого утверждения выглядит так:

X! = (X – 1)! * X, где 0! = 1

Последняя формула используется в функции Factorial для вычисления факториала:

function Factorial(X: Integer): Longint; begin if X = 0 then // Условие завершения рекурсии Factorial := 1 else Factorial := Factorial(X - 1) * X; end;

Вызов функции выглядит следующим образом:

var f: longint; begin f:=Factorial(4); // 4! = 1 * 2 * 3 * 4 = 24 ShowMessage(inttostr(f)); end;

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

Решить эту же задачу с помощью цикла.

Function Fact(N:integer) : LongInt; Var   i : integer; //переменная цикла   Res : LongInt; //результат Begin   Res := 1;   for i := 1 to N do     res := Res*i;   NonResFact := Res; End;

Бывает встречается такая рекурсия, когда первая подпрограмма вызывает вторую, а вторая — первую. Такая рекурсия называется косвенной. Очевидно, что записанная первой подпрограмма будет содержать еще неизвестный идентификатор второй подпрограммы (компилятор не умеет заглядывать вперед). В результате компилятор сообщит об ошибке использования неизвестного идентификатора. Эта проблема решается с помощью упреждающего (предварительного) описания процедур и функций.

6. 2.7.6. Упреждающее объявление процедур и функций

Для реализации алгоритмов с косвенной рекурсией в языке Delphi предусмотрена специальная директива предварительного описания подпрограмм forward. Предварительное описание состоит из заголовка подпрограммы и следующего за ним зарезервированного слова forward, например:

procedure Proc; forward; function Func(X: Integer): Boolean; forward;

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

procedure Proc2(<формальные параметры>); forward; procedure Proc1; begin ... Proc2(<фактические параметры>); ... end; procedure Proc2; // Список формальных параметров опущен begin ... Proc1; ... end; begin ... Proc1; ... end.

Директива forward не нужна, если заголовки подпрограмм объявлены в секции Interface.