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

Некоторый объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя. Рекурсия является мощным средством в определениях; и мы уже использовали ее во внешних спецификациях, а также при задании синтаксиса языка Паскаль (например, рекурсивно определяются такие понятия, как выражение или оператор). Мощность рекурсии связана с тем, что она позволяет задать бесконечное множество объектов с помощью определения конечного "размера". Очень важно, что язык Zonnon допускает использование рекурсии при описании подпрограмм. Например, любой цикл с условием на продолжение

while B do S end

может быть реализован вызовом следующей процедуры, содержащей вызов самой себя:

procedure ЦИКЛ; begin if B then S; ЦИКЛ end end ЦИКЛ.

Скажем, что некоторая подпрограмма P содержит обращение к подпрограмме Q, если в тексте Р содержится явное обращение к Q или к некоторой такой подпрограмме R, что R содержит обращение к подпрограмме Q (заметим, что приведенное определение рекурсивно!). Подпрограмма называется рекурсивной, если она содержит обращение к самой себе. Таким образом, использование рекурсии не всегда сразу видно из текста программы.

С подпрограммой связано множество локальных объектов, новые экземпляры которых создаются каждый раз, когда подпрограмма вызывается. Например, следующая Zonnon-программа осуществляет обращение любого непустого слова (последовательности символов), находящегося во входном файле:

module СЛОВО;
    procedure ОБРАЩЕНИЕ;
        var A : Char;
    begin if ~Eof then read(A); ОБРАЩЕНИЕ; write(A) end end ОБРАЩЕНИЕ;
begin ОБРАЩЕНИЕ end СЛОВО.

Хотя при исполнении программы СЛОВО сосуществует несколько переменных с именем A (в момент начала печати результата имеется больше экземпляров переменной A, чем длина входного слова), не возникает никаких конфликтов при использовании имен: идентификатор A всегда ссылается на локальную переменную с именем A, созданную последней, т.е. на тот экземпляр переменной A, который был создан при последнем обращении к процедуре ОБРАЩЕНИЕ. Это правило доступности поколений (экземпляров) локальных переменных относится не только к процедуре ОБРАЩЕНИЕ, но и к любой рекурсивной подпрограмме, причем распространяется на все ее параметры-значения. Например, пусть имеется

procedure ФАКТ (N:Integer):Integer;
begin if N $>$ 1 then ФАКТ := N $\ast$ ФАКТ(N-1) else ФАКТ :=1 end end ФАКТ;

тогда при обращении ФАКТ(5) сначала заводится пять переменных с именем N, в которых последовательно запоминаются значения 5,4,3,2,1, а затем осуществляется вычисление результата по следующей формуле

5 $\ast$ (4 $\ast$ (3 $\ast$ (2 $\ast$ (1)))).

Аналогично циклам рекурсивные подпрограммы могут описывать процессы вычисления, которые никогда не завершаются. Например, процедура

procedure БесконечнаяПечать;
begin Write('$*$'); БесконечнаяПечать end БесконечнаяПечать;

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