![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Выполнение рекурсивной процедурыСтр 1 из 4Следующая ⇒
Когда объявление процедуры включает процедурный оператор с собственным именем этой процедуры – рекурсивный вызов - ничего особенного не происходит. Вновь объявленные переменные и параметры скрывают одноименные объявленные ранее. Ничего особенного также не происходит при завершении выполнения процедуры. Экземпляры переменных и параметров, созданные при последнем запуске процедуры исчезают, становятся доступны одноименные копии из предыдущего запуска и выполняются операторы, следующие за процедурным оператором.
Поскольку каждый вызов рекурсивной процедуры использует те же имена локальных переменных (и обычно те же имена параметров), существует возможность коллизии значений связанных с этими именами. Отслеживание значений требует аккуратности, но не отличается сильно от рассмотренного ранее случая без рекурсии. Рассмотрим рекурсивную процедуру в следующей программе.
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
|