Рекурсия
В связи с рассмотрением деревьев уместно разобрать понятие рекурсии и его роль в прграммировании вообще и в Паскале в частности. Рекурсией называется использование при программировании процедуры в качестве оператора вызова этой же процедуры. Возможна опосредованная рекурсия, когда первая процедура вызывает вторую, а вторая процедура - первую. Основу для использования рекурсии составляют такие ситуации, когда подслучай общего случая подобен общему случаю и может быть проанализирован с помощью того же алгоритма, что и общий случай. Мы уже встречались с рекурсивным вызовом при решении задачи нахождении числа простых делителей натурального числа n. Аналогичная ситуация возникает в большинстве задач оперирования с деревьями индексов.
Особенность бинарных деревьев вообще и способа их описания с помощью указателей в частности заключается в том, что поддерево, образованное всеми потомками левого и правого сына корневой вершины, по своей структуре идентично самому дереву. Более того, для задания этого поддерева, как и для задания всего дерева, достаточно иметь указатель на корневую вершину поддерева. В этих условиях, например, задача перечисления всех вершин индексного инарного дерева в порядке возрастания решается следующей тривиальной рекурсивной процедурой (тип записи pterm определен в предыдущей главе):
procedure
write_list (pt: pterm); {Процедура вывода дерева (в файл или на печать}
begin
if pt^.left <> Nil then write_list (pt^.left); {Вывести левое поддерево}
write_term (pt^.num); {Вывести запись, соответствующую корню}
if pt^.right <> Nil then write_list (pt^.right) {Вывести правое поддерево}
end;
Также с помощью рекурсивных процедур можно реализовать алгоритм поиска записи в файле с помощью индексного дерева, который был приведен в предыдущей главе:
function find_rec (pt: pterm; v: type_val {тип записи поля упорядочения}): longint;
{Возвращает по указателю на корень и индексному значению номер записи или -1, если запись не найдена}
begin
if pt^.val=v then find_rec:=pt^.num; {Запись соответствует корню дерева}
else
if pt^.val>v then {Запись надо искать в левом поддереве}
if pt^.left = Nil {Левое поддерево отсутствует}
then find_rec := -1 {Запись не найдена}
else find_rec: = find_rec (pt^.left, v) {Запись ищется в левом поддереве}
elseif pt^.val<v then {Запись надо искать в правом поддереве}
if pt^.right = Nil {Правое поддерево отсутствует}
then find_rec := -1 {Запись не найдена}
else find_rec := find_rec (pt^.right, v) {Запись ищется в правом поддереве}
end;
При записи рекурсивных процедур на Паскале возникает одна маленькая проблема. В вышеприведенной программе компилятор узнает обращение к процедуре find_rec внутри процедуры find_rec, поскольку заголовок функции расположен ранее, чем вызов функции. Но если есть две функции, вызывающие друг друга, то один из вызовов обязательно будет раньше, чем заголовок соответствующей функции. Для того, чтобы разрешить это противоречие, в Турбо-Паскале разрешается записывать только заголовок функции или процедуры без тела процедуры. Такое предварительное объявление обозначается ключевым словом forward так, как это делается в следующем примере:
procedure p1(n: integer) forward;
procedure p2 (i,j: integer);
begin ... p1(4); ... end;
procedure p1;
begin ... p2(5,6); ... end;
Заметим, что во втором заголовке процедуры p1 нет необходимости указывать все реквизиты, поскольку они уже специфицированы в первом заголовке.
Другие примеры рекурсивных процедур и функций будут приведены в следующей главе.
