1.2. Рекурсивные процедуры и функции. Взаиморекурсия.
Рекурсивной процедурой называется такая процедура, которая в процессе выполнения вызывает сама себя.
Различают следующие виды рекурсии:
Прямая или явная рекурсия характеризуется существованием в теле процедуры оператора обращения к самой себе.
Косвенная или неявная рекурсия образуется в случае цепочки вызовов других процедур, которые в конечном итоге приведут к вызову начальной.
Для описания на Паскале прямой рекурсии никаких дополнительных операторов не требуется. При описании неявной рекурсии возникает проблема: при определении первой из нескольких взаиморекурсивных процедур или функций возникает необходимость обращения к подпрограмме, которая еще не определена, что в Паскале недопустимо. В этом случае используется специальная директива Паскаля forward, которая позволяет выполнять предописание:
сначала задаются прототипы подпрограмм с параметрами, за которыми вместо тела подпрограммы следует forword;
затем описываются тела этих подпрограмм (причем параметры второй раз можно уже не описывать).
Например, описание взаиморекурсивных процедур A и B можно выполнить следующим образом: procedure B(j:byte);forward;
begin ... B(i); ... end;
procedure B;
begin ... A(j); ... end;
Рис.2.
1.3. Фрейм активации.
Каждое обращение к процедуре вызывает независимую активацию этой процедуры. С процедурой принято связывать некоторое множество локальных объектов (переменных, констант, типов и процедур), которые определены локально в этой процедуре, а вне ее не существуют или не имеют смысла. Совокупность данных, необходимых для одной активации называется фреймом активации.
Фрейм активации содержит независимые копии всех локальных переменных и формальных параметров процедуры, в которых оставляют "следы" операторы текущей активации.
Если процедура обращается к себе несколько раз, образуется несколько одновременно существующих активаций и, соответственно, несколько фреймов активации. Обычно все фреймы являются различными экземплярами одной и той же структуры и размещаются в стеке. При некотором количестве вызовов возможно переполнение стека. На размер фрейма активации влияет способ передачи параметров в процедуру: при использовании параметров-переменных фрейм содержит адреса данных (по 4 байта на каждый параметр), а при использовании параметров-значений - сами данные, которые могут занимать достаточно много места (например, массивы).
Размер фрейма активации можно примерно определить следующим образом:
V= <размер области параметров>+2(адрес возврата)+2..8(для сохранения содержимого регистров)+<размер области локальных переменных>+<размер строки результата, если это функция, возвращающая результат - строку>
Пример 4. Вычисление НОД двух чисел (алгоритм Евклида).
Базисное утверждение: Если два числа равны, то их НОД равен этим числам.
Рекурсивное утверждение: НОД двух чисел равен НОД их разности и меньшего из чисел.
Таким образом, редуцирование происходит при замене большего из чисел на их разность.
Рекурсивная подпрограмма может быть реализована и как процедура и как функция. При реализации в виде процедуры в список параметров добавляется параметр R, передаваемый по ссылке, через который процедура возвращает результат. Схема алгоритма рекурсивной процедуры и текст программы, содержащей рекурсивную процедуру, представлены ниже.
program ex;