Выполнение рекурсивной процедуры

Когда объявление процедуры включает процедурный оператор с собственным именем этой процедуры – рекурсивный вызов - ничего особенного не происходит. Вновь объявленные переменные и параметры скрывают одноименные объявленные ранее. Ничего особенного также не происходит при завершении выполнения процедуры. Экземпляры переменных и параметров, созданные при последнем запуске процедуры исчезают, становятся доступны одноименные копии из предыдущего запуска и выполняются операторы, следующие за процедурным оператором.

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

PROGRAM RunReverse(INPUT, OUTPUT);

PROCEDURE Reverse (VAR File1: TEXT);

VAR

Ch: CHAR;

BEGIN {Reverse}

IF NOT EOLN(File1)

THEN

BEGIN

READ(File1, Ch);

Reverse(File1);

WRITE(Ch)

END

END; {Reverse}

BEGIN {RunReverse}

Reverse(INPUT);

WRITELN;

END. {RunReverse}

Выполнение:

INPUT: AB

OUTPUT: BA

Для INPUT AB процедура была вызвана три раза. Первый раз в процедурном операторе программы, два последних раза – в процедурном операторе внутри процедуры. Каждый такой процедурный оператор выполняет блок процедуры, начинающийся с объявления VAR. Каждое такое объявление создает новую копию переменной Ch, и Паскаль-машина сохраняет и скрывает ранее объявленную переменную с таким же именем.

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

1) переменная Ch для текущего запуска процедуры исчезает, открывая раннее скрытую Ch

2) выполняется следующий оператор

Для двух последних запусков следующим оператором будет WRITE(Ch), после выполнения первого оператора, выполняется WRITELN и программа завершается.

Таблица выполнения, приведенная ниже показывает в деталях, что происходит:

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

PROGRAM RunCopy(INPUT, OUTPUT);

PROCEDURE Copy (VAR File1: TEXT);

VAR

Ch: CHAR;

BEGIN {Copy}

IF NOT EOLN(File1)

THEN

BEGIN

READ(File1, Ch);

WRITE(Ch);

Copy (File1)

END

END; {Copy}

BEGIN {RunCopy}

Copy(INPUT);

WRITELN;

END. {RunCopy}

Выполнение:

INPUT: AB

OUTPUT: BA

В итеративной версии копирования каждый символ перемещается из входного файла через переменную программы в выходной файл. Рекурсивная версия совсем по иному. Каждый символ сохраняется в отдельной локальной переменной и все они существуют в Паскаль-машине одновременно. Эти сохраненные в локальных переменных символы могут быть потом использованы, как в следующем примере, программе, которая копирует входные символы, потом добавляет их в обратном порядке.

PROGRAM RunPalindrome(INPUT, OUTPUT);

PROCEDURE Palindrome(VAR File1: TEXT);

VAR

Ch: CHAR;

BEGIN {Palindrome}

IF NOT EOLN(File1)

THEN

BEGIN

READ(File1, Ch);

WRITE(Ch);

Palindrome (File1)

WRITE(Ch)

END

END; {Palindrome}

BEGIN {RunPalindrome}

Palindrome (INPUT);

WRITELN

END. {RunPalindrome}

Выполнение:

INPUT: AB

OUTPUT: ABBA

INPUT: 123456789

OUTPUT: 123456789987654321