14.3. Рекурсии

В языке паскаль процедуры и функции могут вызывать сами себя, т. е. обладать свойством рекурсивности.

Пример. Выдать на печать в обратном порядке цифры целого положительного числа N. Составим процедуру REVERSE PROCEDURE REVERSE (N:INTEGER);

Рассмотрим работу этой процедуры для числа N = 153. Оператор WRITE (N MOD 10) выдает в файл OUTPUT остаток от деления числа 153 на 10, т. е. последнюю цифру 3. Оператор IF (N DIV 10) <> 0 THEN REVERSE (N DIV 10)

проверяет целую часть частного 153/10 = 15 на ноль. Если целая часть не ноль, то с этим значением (15) идет вновь обращение к процедуре REVERSE. Оператор WRITE (N MOD 10) дописывает в файл OUTPUT остаток отделения 15 на 10, т. е. 5; затем со значением 15/10 = 1 идет обращение к REVERSE. После вывода цифры 1 оператором WRITE (N MOD 10) проба N DIV 10 на ноль передает управление на конец процедуры. В файле OUTPUT будет записано число 351. Его можно выдать оператором WRITELN.

Таким образом, однократное обращение извне к процедуре REVERSE вызвало трехкратное ее срабатывание. Условие полного окончания работы рекурсивной процедуры должно находиться в самой процедуре (иначе произойдет зацикливание).

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

Пример. Если А, В - имена модулей, то схема вызова может быть такой: А → В → А.

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

здесь - Р - имя процедуры, FORWARD - ключевое слово. Это описание указывает транслятору, что текст процедуры Р помещен ниже.

Подобным же образом описывается функция: к оператору FUNCTION добавляется слово FORWARD. Список формальных параметров и тип результата (для FUNCTION) включается только в это предварительное описание и опускается в заголовке соответствующего модуля.

Пример. Пусть функция В при работе вызывает функцию \ которая, в свою очередь, вызывает функцию В. Тогда эти модули можно описать так;

Заголовок (FUNCTION В) перед текстом функции В содержит Только имя этой функции (список формальных параметров и тип функции не указываются).