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

1.3. Косвенная рекурсия и опережающее описание

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

Procedure A(i: Byte);

Begin

.

B(i);

.

end;

procedure B(j: Byte);

.

begin

.

A(j);

.

end;

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

Procedure B(j: Byte); forward;

Procedure A(i: Byte);

Begin

.

B(i);

.

end;

procedure B;

begin

.

A(j);

.

end;

Как видим, опережающее описание заключается в том, что объявляется лишь заголовок процедуры В, а её тело заменяется стандартной директивой FORWARD. Теперь в процедуре А можно использовать обращение к процедуре В – ведь она уже описана, точнее, известны её формальные параметры, и компилятор может правильным образом организовать её вызов. Обратим внимание: тело процедуры В начинается заголовком, в котором уже не указываются описанные ранее формальные параметры.

1.4. Рекурсивные структуры

1.4.1. Список

Список относится к особой группе структур - это так на­зы­ва­е­мые ре­курсивные структуры.

Приведем рекурсивное определение списка: Списком называется со­­во­купность связанных элементов, из которых один является осо­бым элементом (первым, "головой"), а все остальные образуют спи­сок. Рекурсивные структуры в программировании замечательны тем, что мно­гие операции по их обработке можно эффективно реализовать с использованием рекурсивных процедур, которые отличаются боль­шой ла­коничностью и наглядностью. В качестве примера приведём про­це­ду­ру проверки, является ли Н1 подсписком списка Н:

TYPE Указатель = POINTER TO Элемент;

Элемент = RECORD

INFO : Инфоpмация;

LINK : Указатель;

END

PROCEDURE Проверка (Н,Н1 : Указатель) : BOOLEAN;

BEGIN

IF H # NIL THEN

RETURN (Н = Н1) OR Проверка (Н^.LINK, Н1)

ELSE RETURN (Н = Н1)

END

END Проверка.

Проверка (H # NIL) в этом примере нужна только для того, что­бы предотвратить попытку интерпретировать пустую ссылку как эле­мент списка при вызове Проверка (H^.LINK, H1). Ситуация (H=H1=NIL) рассматривается как положительный результат проверки.

1.4.2. Набор

Другим примером рекурсивной структуры является структура на­бора, которая определяется следующим образом: Набором называется совокупность связанных элементов, каждый из которых может быть ли­бо атомом, либо набором. Атом определяет "неделимый" элемент на­бора, предназначенный для хранения элементарной порции ин­фор­ма­ции. Реализация наборов основана на использовании разнородных списков. Например, ниже приведена (см. рис. 1) одна из возможных структур на­бо­ров. В этой структуре H1 - набор из четырех элементов (a, b, H2, c), из них H2 - набор, остальные - атомы. H2 состоит в свою очередь из тpех элементов - атома c и двух наборов H3 и H4, причем набор H3 - пуст (не содержит элементов), а H4 содержит два атома (d и f).

H2

H1

H3 H4

					f