РЕКУРСИВНЫЕ МЕТОДЫ В ПРОГРАММИРОВАНИИ

Редактор Л. БабынинаХудожник В. Новоселова Художественней редактор В. ШаповаловТехнический редактор Г. Алюлина. Корректор Е. Кочегарова

Сдано в набор 22/Ш 1974 г. Подписано к печати 8/VIII 1974 г. Бумага тип. № 2 60Х90716=2,5 бум. л. Усл. печ. л. 5,0. Уч.-изд. л. 4,2. Изд. № 1/7516. Цена 31 к. Зак. 155 ИЗДАТЕЛЬСТВО «МИР» Москва, 1-й Рижский пер., 2

Ордена Трудового Красного Знамени

Ленинградская типография № 2 имени Евгении СоколовойСоюзполиграфпрома при Государственном комитете Совета Министров СССРпо делам издательств, полиграфии и книжной торговли.

198052, Ленинград, Л-52, Измайловский проспект,.29

ББ20204-038041(01)—7420204-038041(01)—7438-7438-74© Перевод на русский язык, «Мир», 1974© Перевод на русский язык, «Мир», 1974

Б

Б

20204-038

041(01)—74

20204-038

041(01)—74

38-74

38-74

© Перевод на русский язык, «Мир», 1974

© Перевод на русский язык, «Мир», 1974

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДАИ ПЕРЕВОДЧИКА

Широкое проникновение рекурсивных методов в практику программирования началось с распространением универсального языка программирования АЛГОЛ-60, допускающего рекурсивные обращения к процедурам. На первых порах аппарат процедур, введенный авторами АЛГОЛа, казался совершенно необычным и вызывал недоумение. Однако практика показала, что разумное применение рекурсии с последовательным сокращением количественной сложности задач, возникающих в процессе рекурсивных обращений, является весьма эффективным методом программирования, существенно упрощает запись различных сложных алгоритмов, а в ряде случаев оказывается практически незаменимым средством. Рекурсия отражает существенную характерную черту абстрактного мышления, проявляющуюся при анализе сложных алгоритмических и структурных конструкций в самых различных приложениях. Дело в том, что, пользуясь рекурсией, мы избавляемся от необходимости утомительного последовательного описания конструкции, и ограничиваемся выявлением взаимосвязей между различными уровнями этой конструкции.

В настоящее время область практического применения рекурсии весьма широка. Она включает, в частности, сложные задачи численного анализа, алгоритмы трансляции, а также различные операции над списками, являющиеся необходимым аппаратом разработки современных автоматизированных систем управления. Поэтому аппарат рекурсии предусматривается практически во всех языках программирования, появляющихся после АЛГОЛа.

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

Э. 3. Любимский ■ В. В. Мартынюк

ПРЕДИСЛОВИЕ

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

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

Д. В. Баррон

11ОСНОВНЫЕ ПОНЯТИЯ РЕКУРСИИ

1

1

Введение

Существует мнение [1], что «если бы в средние века были вычислительные машины, то одни программисты сжигали бы на кострах других программистов за ересь». Почти наверняка самой страшной ересью считалась бы вера (или неверие) в рекурсию. Достоинства и недостатки рекурсии как средства программирования подвергались широкому обсуждению в течение последних нескольких лет. Как нередко бывает в таких ситуациях, имеется тенденция к сохранению крайних взглядов и к рассмотрению проблемы либо в черном, либо в розовом свете. Одни утверждают, что всегда лучше пользоваться не рекурсией, а итерацией. Другие же настолько верят в рекурсию, что они нс снисходят до включения очевидных методов итерации в разрабатываемые ими языки программирования. Автор придерживался при написании этой книги промежуточной позиции, избегая крайних точек зрения. По возможности предмет излагается с учетом перспектив, демонстрируются способы успешного применения рекурсии в различных ситуациях, выявляются соотношения между рекурсией и более известными итеративными методами. Автор старается показать также влияние рекурсивных методов на программное и аппаратное обеспечение вычислительных систем.

Рекурсивные функции и процедуры

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

factorial № = пХ factorial (п — 1), если п ^= О factorial (0) = 1

Здесь factorial (п) определяется через значение factorial (п— 1), которое определяется через factorial (п —2), и т. д. до сведения к значению factorial (0), которое определено явно и равно 1. Любое рекурсивное описание должно содержать явное

определение для некоторых значений аргумента (или аргументов), так как иначе процесс сведения оказался бы бесконечным. Для таких описаний удобна запись условного выражения, которую впервые ввел Маккарти [2]. Условные выражения представляются в форме

[61—>^1, Ь^—* е^ ...еп]

Здесь bi — логическое условие, которое может'быть истиной или ложью, вг — выражение. Значение условного выражения получается проверкой значений bi по очереди слева направо до встречи первого значения «истина»; соответствующее значение ei берется в качестве значения всего выражения. Если все условия bi ложны, то выражение принимает значение еп. Таким образом описание факториальной функции имеет вид

factorial (п) = [(п = 0) -> 1, п X factorial (/г — 1)]

Другим примером рекурсивного описания функции может служить рекуррентное соотношение между функциями Бесселя различных порядков с одинаковыми аргументами, например:

Если записать 7п(х) в симметричном обозначении 7(и, х) и заменить п на значение п— 1, то рекуррентное соотношение принимает вид

7 (га, х)= 2i-^7(ra — ^ x)_/(ra_2> х)

Таким образом, если для данного аргумента х известны значения /о и /ь то можно записать определение 7(га, х) в виде

Цп, х) = [(га = 0)-> 7 (0, х), (га — !)->/(!, х),

((2 (га — 1)/х) 7 (га — 1, х) — 7 (га — 2, х))]

Еще одна возможная форма рекурсии встречается тогда, когда процесс описывается через подпроцессы, один из которых идентичен основному процессу. Например, рассмотрим двойной интеграл

J J f(x,y)dxdy а с

Один из методов вычисления состоит в представлении двойного интеграла с помощью двукратного простого интегрирования b / d\

J I J f (^ У^У) dxа 'с'

Для вычисления внешнего интеграла требуется знать значения подинтегрального выражения в выбранных точках, а для вычисления подинтегрального выражения требуется интегрирование, так что подпроцесс идентичен основному процессу.

Определенный интеграл

7 = J F^dxа

является, разумеется, функцией от а и 6, так как значение I зависит от значений а и Ь. Можно также сказать, что / является функцией от F, так как при изменении функции F изменяется значение интеграла. Итак, мы приходим к записи / как функции от трех переменных

1 = Ца, 6, F)

Мы ввели здесь понятие, которое не встречается в обычной математике, а именно переменную, представляющую функцию. Важно чувствовать разницу между величиной F, представляющей функцию, и величиной Г(3), представляющей результат применения функции к аргументу. Например, если

F (х) = 1 + х2

то Г(2)—это число 5, а символ F, взятый отдельно, представляет операцию «возведение аргумента в квадрат и прибавление единицы». Обычно традиционная математика имеет дело с числами того или иного вида. При этом не встречаются функции без аргументов и нет необходимости их различать. Но программирование имеет дело с процессами, и может возникнуть желание говорить о процессе независимо от объектов, над которыми процесс выполняется. Для описания функций как абстрактных понятий можно применять «лямбда-исчисление», разработанное Черчем [4]; подробнее ознакомиться с таким подходом можно по книге Хигмана [15].

Рассматриваемое различие не отражено в большинстве языков программирования. Например, на АЛГОЛе можно написать

real procedure куб (z/); value у; real у;

begin куб*. = уХуХУ end;

Эта процедура присваивает значение непосредственно переменной куб, несмотря на то, что обращение к процедуре содержит аргумент, например:

а: = куб(ЬУ, .

Явное различие делается в языке ЛИСП, где допускаются функции, результатами применения которых являются функции.

Аналогичные возможности предусмотрены в языке CPL, допускающем переменные типа функций; поэтому можно записать

let fbe function

f: = b—> Sin, Cos

a: = f[c]

Таким образом, мы можем представить интеграл

6

Л = J F (х) dxа

как функцию от а, 6 и F, но не от х, поскольку значение /1 не изменяется, если х всюду заменяется на z. Двойной интеграл

b d

/2 = J J F^x, y)dxdyа с

является функцией от a, b, с, d и F (но не от х и не от у) и может быть записан как

Ц = 1Ла^ Ь, с» d, F)

Предположим теперь, что мы котим описать Л через /1 (т. е. получить формальное представление процесса двойного интегрирования в виде двукратного просгсго интегрирования). Введем вспомогательную функцию

G^y^F^x, у)

Тогда

/2 = Л(а, Ь, I^c, d, G))

Теперь появилась рекурсия, поскольку функция /1 присутствует как аргумент в обращении к Л; это типичный пример рекурсивного использования процедуры. Следует отличать такую рекурсию от другого типа рекурсии, при котором функция присутствует в правой части своего описания.

В случае двойного интеграла вычисление одного интеграла требует вычисления другого интеграла; второй интеграл вычисляется непосредственно. Принято говорить в таких случаях, что рекурсия имеет один уровень глубины-, это означает, что процесс обращается к себе как к подпроцессу только один раз. Для рекурсивно описанной функции глубина рекурсии — это число промежуточных вычислений функции в процессе ее вычисления для

данного аргумента или набора аргументов1). Например, при вычислении функции factorial (3) в соответствии с рекурсивным описанием нужно вычислить factorial (2), factorial (1) и factorial (0); в этом случае рекурсия имеет глубину в три уровня. Для факториальной функции глубина рекурсии при любом заданном значении аргумента видна сразу. Однако это — исключение, а обычно глубина рекурсии нс является очевидной даже при простейших описаниях. Например, рассмотрим алгоритм Эвклида для вычисления наибольшего общего делителя (НОД) двух положительных целых чисел. Этот алгоритм может быть описан следующим образом:

НОД (riy m) = [т > п—> НОД (т»

т = 0->Пу НОД(Шу Ост^Пу т)^ (Ост^Пу т)—функция, значением которой является остаток от деления п на т.) В этом описании отражено следующее правило: если т является точным делителем п, то НОД = т, а в противном случае нужно брать функцию НОД от т и от остатка, получаемого при делении п на т. Первая строка в описании всего лишь позволяет писать аргументы в любом порядке. Хотя это описание и является достаточно простым, все же сразу нс очевидно, какая глубина рекурсии будет достигнута при вычислении, например, значения НОД (385, 1105). В общем случае можно утверждать, что рекурсивное использование процедуры требует очевидной конечной глубины рекурсии, тогда как вычисление рекурсивно описанной функции влечет за собой неопределенную глубину рекурсии, зависящую от значений аргументов. (Если описание предназначено для практических вычислений, то глубина рекурсии должна быть конечной. Бесконечное по глубине рекурсивное описание называется регрессивным. Некоторые рекурсивные описания могут иметь конечную глубину рекурсии при одних входных данных и бесконечную при других. Теоретически невозможно определять с помощью единого алгоритма, окажется ли произвольное описание конечным в любом случае, однако часто можно показать, будет ли в отдельных случаях глубина рекурсии конечной или бесконечной.)

Оба типа рекурсии могут присутствовать одновременно. Наиболее известным примером такого сочетания является функция Аккермана:

А (т, п) = \т = 0->пА- 1,

п = 0~> А(т— 1, 1),

А^т— 1, А(^ту п— 1))]

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

(Напоминаем, что при вычислении условного выражения условия проверяются по очереди, так что вторая и третья строки будут достигнуты только, если m #= 0.) Кажущаяся простота этой функции является обманчивой. Читатель, располагающий временем, может попытаться вычислить значение Л (2,3), исходя из этого определения.

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

Обработка рекурсивных данных

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

(Л 0 В)

где 0— один из знаков '+', —, X или / и Л, В — либо наименования переменных, либо скобочные выражения, например:

^a-V^b-VkcXd^-e^

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

Аналогичная ситуация возникает при обработке списков. Списковая структура может быть описана как размещение объектов, называемых атомами, в соответствии со следующими правилами.

Список либо ПУСТОЙ, либо состоит из начала, представляющего собой либо атом, либо список, и из остатка, который

является списком. Например:

<(Л, В\ (С, D\ Е) Начало (Л, В)<(Л, В\ (С, D\ Е) Начало (Л, В)Остаток ((С, D), Е^Остаток ((С, D), Е^

<(Л, В\ (С, D\ Е) Начало (Л, В)

<(Л, В\ (С, D\ Е) Начало (Л, В)

Остаток ((С, D), Е^

Остаток ((С, D), Е^

Начало ЛОстаток (В)Начало ВОстаток ПУСТОЙНачало ЛОстаток (В)Начало ВОстаток ПУСТОЙНачало (С, D^Начало (С, D^Остаток (В)Остаток (В)Начало СОстаток (В)Начало СОстаток (В)Начало (В)Остаток ПУСТОЙНачало (В)Остаток ПУСТОЙНачало DОстаток ПУСТОЙНачало DОстаток ПУСТОЙ

Начало Л

Остаток (В)

Начало В

Остаток ПУСТОЙ

Начало Л

Остаток (В)

Начало В

Остаток ПУСТОЙ

Начало (С, D^

Начало (С, D^

Остаток (В)

Остаток (В)

Начало С

Остаток (В)

Начало С

Остаток (В)

Начало (В)

Остаток ПУСТОЙ

Начало (В)

Остаток ПУСТОЙ

Начало D

Остаток ПУСТОЙ

Начало D

Остаток ПУСТОЙ

Эта структура описана рекурсивно, и поэтому естественно применить к ней методы рекурсивной обработки. Например, для копирования списка мы пишем (см. [3] или [5])

Copy ^ = VNull^-> ПУСТО» Cons (Copy (Hd(z))f Сору (Т1 (г)))]

Это рекурсивное описание функции1) в точности отражает рекурсивную структуру данных. Примеры рекурсивных функций для обработки списков будут приведены в гл. 2, а краткое описание списковых структур дается в приложении.

Рекурсия в языках программирования

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

Рекурсия вошла в программирование в значительной степени благодаря системам обработки списков IPL [6] и ЛИСП [7], а также языкам АЛГОЛ-58 [8] и АЛГОЛ-60 [9, 10]. Мы не хотим этим сказать, что рекурсия не применялась прежде, однако те, кто использовали ее раньше, вероятно, не удостаивали этот метод специального термина. Рекурсия естественно появилась в ЛИСПе, который является функциональным языком (см. разд. 1.5) и связан с обработкой списковых структур,

*) Здесь Сору — копия, Null — пустой, Cons — объединение, Hd — начало, Т1 — остаток. — Прим, перев.

рекурсивных по самой своей природе. Тот факт, что АЛГОЛ допускает рекурсию, вызван разнообразными причинами, поскольку нужда в рекурсии при решении задач численного анализа не столь очевидна. Некоторые приверженцы АЛГОЛа утверждают, что наличие рекурсии является его основным преимуществом перед другими языками типа ФОРТРАНа. Это послужило поводом для контрутверждений, что «все рекурсивные связи могут быть сведены к рекуррентным или итеративным описаниям» [И]. Хотя это утверждение и справедливо для рекурсивно определенных функций, оно неверно для рекурсивного использования процедур (иногда называемого косвенной рекурсией), которое, как мы видели, имеет важное значение для численного анализа.

Различие между «рекурсивным» языком типа АЛГОЛа и «нерекурсивным» языком типа ФОРТРАНа состоит в том, что на ФОРТРАНе программист, желающий пользоваться рекурсией, должен разработать для себя соответствующий аппарат, тогда как на АЛГОЛе этот аппарат обеспечивается системой, так сказать «за кулисами». Во многих рекурсивных системах за это приходится платить тем, что автоматический аппарат, предусмотренный для обеспечения рекурсии, вступает в действие даже тогда, когда программа не является рекурсивной; это приводит к напрасным затратам машинного времени. Разумеется, существуют различные способы организации рекурсии, некоторые из них будут весьма подробно рассмотрены в следующих главах. Программист может указывать, какие функции или процедуры являются рекурсивными, а какие нет, или же достаточно развитый компилятор может сам выяснять это для себя. Однако все это неидеальные решения, так как, даже если какой-то процесс может быть представлен итеративно, его рекурсивное описание может оказаться значительно более простым. Поэтому было бы выгодно сочетать легкость написания рекурсивных описаний с высокой скоростью выполнения итеративного процесса, и лучший способ достижения этой цели состоит в изменении традиционной машинной аппаратуры. (Это реализовано по крайней мере в одной машине — см. [12, 13].) Теоретическое изучение соотношений между рекурсивными и итеративными "программами показывает, что иногда возможно переводить рекурсивное описание в эквивалентную итеративную программу; такое преобразование описывается более подробно в гл. 4.

Рекурсия в функциональном программировании

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

удобства, позволяя более сжато описывать подлежащий выполнению алгоритм. Еще одна ситуация, когда применение рекурсии является обязательным, возникает при использовании функциональных языков программирования, которые по самой своей природе не могут обеспечить каких-либо средств для явной итерации.■

Большинство языков программирования научных расчетов является «операторными» языками, в которых программа состоит из последовательности обязательных команд, например:

а: = 6+ с напечатать (а)

Показателем возрастания сложности языков программирования является то, что в основной «скелет» команды могут подставляться все более и более сложные выражения. Например, в одном из ранних языков (автокоде Пегас) переменные идентифицировались именами у1, и2, уЗ и т. д. и операторы присваивания имели простую форму

у! = у2 0 уЗ

где 0 означает одну из четырех арифметических операций +', —, X или /. В более развитом языке (автокоде Меркурий) допускались простые скобочные выражения, например:

Л^В + С^В + С) —G

а в современных языках допускаются вложенные скобки, например:

ИТОГ = (СУММА + СЧЕТЧИКУ РАЗНОСТЬ —

— (АИТОГ + БИТОГО • 14169

Язык CPL [3] доводит эту тенденцию до ее логического завершения, разрешая писать выражения слева от знака присваивания, например ):

(х = 0 -> а, Ь): = (((а + Ь^с — d)e + f)

В рамках операторного языка повторение обеспечивается непосредственными командами, например, на ФОРТРАНе:

DO 10 / = 1,5

Л = А + В(/)

10 CONTINUE

или на АЛГОЛе:

for х: = a step b until с do beginend

Операторный язык требует, чтобы программист явно представил последовательность выполнения своей программы. Часто эта последовательность может оказаться несущественной; программист мог бы потребовать, чтобы выполнились некоторые- действия, не касаясь порядка, в котором они должйы производиться. При однопроцессорной машине эта необходимость указания последовательности только причиняет неудобство, но при многопроцессорной машине она является настоящей обузой, поскольку мешает программисту извлекать выгоду из того факта,, что несколько работ могут выполняться одновременно. (По этой причине язык PL/1 включает описательные предложения, в которых указываются требуемые последовательностные соотношения между блоками программы.) Впрочем, даже в языке с командной структурой последовательность действий не всегда оговаривается явно. Например, рассмотрим следующие два варианта:

(а) ТЕМР1 = В4-С(б) G = (B + C)*(E + F)

ТЕМР2 = В + В

G = TEMPI* TEMP 2

Если нас не интересуют значения TEMPI и ТЕМР2, то это эквивалентные части программы. Однако во втором случае последовательность действий подразумевается отношением старшинства между операциями + и * (умножение), а также объединяющей способностью скобок. Функциональное программирование — это метод, в котором такая тенденция доведена до предела, так что последовательность действий совсем не оговаривается явно. Сама программа становится функцией, аргументами которой являются входные данные, а значением — искомый - результат вычислений. Например, программа:

Л = 0-5

В = ЕХР(— Л* Л)

НАПЕЧАТАТЬ (В)

могла бы быть представлена функционально как функция от А НАПЕЧАТАТЬ (ЕХР(— Л* Л))

применяемая к аргументу 0,5; в Х-обозначениях это записывается так:' ‘

ХАЛНАПЕЧАТАТЬ (,ЕХР<-А*А^ [0 • 5)

Здесь опять последовательность действий не оговорена явно. Прежде чем можно будет применять функцию НАПЕЧАТАТЬ, необходимо вычислить ее аргумент; это включает в себя вычисление присутствующей в аргументе функции ЕХР, и таким образом получается правильная последовательность действий.

-Вычислением аргументов функции перед применением этой функции определяется простое следование действий. Однако ^сли вся программа представляется единой функцией, то как можно добиться какого-либо повторения? Это можно сделать, применяя рекурсию: в функциональных программах рекурсия играет ту же роль, что и повторение в программах, состоящих из команд. Например, вычисление factorial (3) в соответствии € рекурсивным определением влечет за собой вычисление facto- rial(2), которое в свою очередь вызывает вычисление factorial (1), так что повторное употребление в описании обеспечивает желаемое повторение при выполнении.

Подсчет с помощью рекурсии

Обычная форма итерации включает известное число повторений. Как правило, это программируется с помощью простого счетчика, но можно использовать рекурсию как способ избежать явного подсчета. Например, предположим, что на некотором этапе компиляции мы хотим исключить из рассмотрения все, что находится после какой-то открывающей скобки вплоть до соответствующей закрывающей скобки (допускаются вложенные скобки). Обычно мы стали бы подсчитывать значения 4-1 для открывающей скобки, —1 для закрывающей скобки и игнорировали бы все остальные символы, пока в счетчик не попадет значение нуль. Если система программирования разрешает использование рекурсивных подпрограмм, то при достижении первой открывающей скобки мы можем вызвать подпрограмму со следующей спецификацией:

Читать следующий символ

Если это „(“, то вызвать ту же подпрограмму рекурсивно Если это „у\ то выйти из подпрограммы, в противном случае уйти на метку 1.

Таким образом, подпрограмма будет выполняться до тех пор, пока не прочтет соответствующую закрывающую скобку; это приведет к заключительной «раскрутке» рекурсии и к передаче управления исходной программе.

Полезна ли рекурсия?

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

то применение рекурсивных методов является более или менее обязательным. Пусть всякий, кто сомневается в этом, попытается написать программу копирования списковой структуры, не прибегая к применению рекурсии. Если задача касается процесса, рекурсивного по самой своей природе, то рекурсия опять- таки обязательна, хотя и может быть замаскирована специальными мерами. Поставленный вопрос приобретает смысл только тогда, когда рассматривается применение процесса, не являющегося существенно рекурсивным, к данным, не имеющим рекурсивной внутренней структуры. В таком случае ответ должен зависеть в какой-то степени от того, стремимся ли мы к машинной эффективности или к удобству для пользователя. Например, любой программист счел бы очевидным вычисление факториальной функции с помощью итеративного цикла, скажем на АЛГОЛе:

integer procedure Factorial (я); value я; integer n;

begin real f; integer i; f: = l;

for i: = 1 step 1 until n do f: = fXi; Factorial: = f end;

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

integer procedure Factorial (п); value п; integer п;

Factorial: = if я = 0 then 1 else n X Factorial (я — 1);

(Вероятно, он предпочел бы опустить несущественную (с его точки зрения) спецификацию «value я; integer я», но мы не можем следовать здесь такой линии поведения. Впрочем, см. [3, 14].).

Чтобы нас не упрекали в искусственности этого примера, рассмотрим описанный ранее алгоритм НОД отыскания наибольшего общего делителя двух чисел. На АЛГОЛе можно написать следующие программы:

НЕРЕКУРСИВНАЯ

integer procedure НОД(п, tn); value я, m; integer я, яг; begin integer я1, ml, р;

if я > яг then begin я1 : = я; ml : = m end else begin я1: = т; ml; = n end;

L: if 0ст(я1, ml) = 0 then НОД ; = ml

else begin

p: ml; ml : = Ост(п1, ml);

я1 : = p; go to L end;

end;

РЕКУРСИВНАЯ

integer procedure НОД(пу m); value и, m; integer n, m;

НОД: = И m>n then НОД(т, zz) else if m = 0 then n else НОД (m, Ост^п, m));

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

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

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

СПИСОК ЛИТЕРАТУРЫ

Gill S., Ann. Rev. Automatic Programming, v. 1, p. 180, ed. R. Goodman, Pergamon, 1960.

McCarthy J., Recursive functions of symbolic expressions and their computation by machine, Commun. Assoc. Computing Machinery, 3, №4 (1960) , 184.

Barron D, W., Strachey C., Programming: ch. 3 of «Advances in programming and non-numerical computation», ed. L. Fox, Pergamon, 1966.

Church A., The calculi of lambda conversion, Princeton University Press, 1941.

Woodward Р. М., List programming, ch. 2 of «Advances in programming and non-numerical computation», ed. L. Fox, Pergamon, 1966.

Newell A. (ed.), Information processing language-V manual, Prentice-Hall, 1961.

McCarthy J., et al, LISP 1-5 programmer’s manual, M. LT. Press, 1965.

Perlis A. J., Samelson K. (ed.), Preliminary report — International algebraic language, Commun. Assoc. Computing Machinery, 1, № 12 (1958), 8.

Naur P. (ed.), Revised report on the algorithmic language ALGOL 60, Commun. Assoc. Computing Machinery, 6, № 1 (1963), 1; Computer J., 5, № 4 (1963), 349. (Русский перевод: Наур П. (под ред.), Алгоритмический язык АЛГОЛ-60, Пересмотренное сообщение, «Мир», М., 1965.)

Dijkstra Е. W., A primer of ALGOL programming, Academic Press, 1962.

Rice A. G., Commun. Assoc. Computing Machinery, 8, № 2 (1965), 114.

Burroughs Corporation, Operational characteristics of the processors for the Burroughs B5000.

Barton R. S., A new approach to the functional design of a digital computer, Proc. Western Joint Computer Conf., 1961, p. 393.

Wirth N., A generalisation of ALGOL, Commun. Assoc. Computing Machinery, 6, № 9 (1963), 547.

Higman B., A comparative study of programming languages, Macdonald, v1967. (Русский перевод: Хигман Б., Сравнительное изучение языков программирования, «Мир», М., 1974.)

2

ПРИМЕРЫ И ПРИЛОЖЕНИЯ

Приложения к вычислениям

Решение уравнений

Вычисление квадратного корня является типичным примером общего класса итеративных процессов, описываемых уравнениями вида

■^л+1 ^ F ^п)

В таких случаях всегда определяются дискриминант d и допуск /, и решение имеет вид S(x0), где х0 — начальное значение и

S^ = \d<t->x, S(F^

В качестве конкретного примера рассмотрим вычисление квадратного корня. Итеративная последовательность для квадратного корня из у имеет вид

^п+1 == "2" (^л + til^n^

Если мы рассматриваем ограниченный интервал у <Z 1, то хорошим начальным значением является V2(l+z/) и рекурсивное определение имеет следующий вид:

Квадратный корень (у) = S^y, V2(l + #))

s(У, х) = ^у)х — x) < 6 -> x, S ^y, у (x + yjx^

На АЛГОЛе получаем следующие программы1):

РЕКУРСИВНАЯ

real procedure Квадратный корень (у)', value у;

begin real procedure S(,y, х); value у, х;

begin S: = if (у/х— х) < 2 X epsilon then х

else S(y, (х Ц-г//х)/2)

end;

Квадратный корень : = S(y, (1 + z/)/2) end;

*) При переводе примеров используется вариант языка АЛГОЛ-60, в котором допускаются идентификаторы, содержащие буквы русского языка и пробелы. — Прим, перев.

НЕРЕКУРСИВНАЯ

real procedure Квадратный корень (у); value у;

begin real х;

х:=(1 + у)/2;

L: if (у/х — х) < 2 X epsilon then Квадратный корень : = х else begin х: = (х + z//x)/2;

go to -L

end;

end;

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

Рекуррентные соотношения

С первого взгляда кажется, что трехчленные рекуррентные соотношения (типа рекуррентного соотношения для функций Бесселя) лучше всего представлять в виде рекурсивных программ:

7 (л, х) = [(л = 0)-> 70,(л=1)-^-7ь

(АХ7(л—1, xWBXH.n-2, х))]

Однако такая программа вычисляет значение J (п, х) весьма неэффективно, так как процесс ее работы включает приблизительно 2П~2 шагов вместо (л— 1) шагов, которые потребовались бы при самом эффективном методе. Например, для вычисления /(5, х) при заданных 7(0, х) и 7(1, х) очевидная последовательность счета состоит в том, чтобы вычислять по очереди 7(2, х), 7(3,х), 7(4,х) и 7(5,х). Однако если пользоваться приведенным выше описанием, то мы получаем (в сокращенной записи)

7s = А74 + BJ3

74 — AI3 + BJ2

1з = AJ2 A" BJ1

7г = AJj -]- BJо

Значения 1г и 73 вычислялись бы дважды, поэтому потребовалось бы 8 шагов.

Маккарти указал следующий способ повышения экономичности программы при сохранении рекурсивного описания. Записываем (по-прежнему в сокращенных обозначениях)

7 (л, х) = 7А(л, 1, 70, 7J

где JA^n, пц а, Ь) = [(п = О)->а,.

кт = п) -> 6,

JA (гц т + 1, b, АЬ + В а)2

При этом 7(5, х)=7А(5, 1, 70, 7J

= 7А(5, 2, 7Ь /2), так как 72 = AJX + BJQ

= 7 Л (5, 3, 72, 73).

= 7Л(5, 4 , 73, 74)*

= 7Л(5, 5 , 74, 75) = 75

Заметим, что эффективность достигается удачным использованием счетчика. Это описание ближе к итеративному, чем к рекурсивному. (Мы вернемся к этому вопросу в гл. 4, где будет рассматриваться связь между итеративными и' рекурсивными процессами.)

Однако существует более общий способ повышения эффективности таких процессов при сохранении истинно рекурсивной структуры описания. Этот способ состоит в использовании известного программистского приема — просмотра таблиц. Применительно к вычислению функции Бесселя мы организовали бы таблицу тех значений 7(п, х), которые уже вычислены, и каждый раз, когда потребовалось какое-то значение J (п,х), проверяли бы сначала, не находится ли оно уже в таблице. Этим обеспечивается фактическое вычисление только нужных значений функций, причем каждое значение вычисляется только один раз. Сохраняется возможность неэффективности за счет линейного просмотра таблицы, но она не имеет прямого отношения к ре- курсивности процедур и может быть устранена различными известными методами, например применением перемешанной таблицы. Пример использования этого приема приводится в разд. 2.1.4. Могло бы показаться, что легче написать нерекурсивную программу, чем организовывать просмотр таблицы, но имеется возможность написать на языке ЛИСП такую программу, которая обрабатывает рекурсивное описание любой функции на ЛИСПе, преобразуя его так, чтобы ни один аргумент не вычислялся более одного раза. (Для языка АЛГОЛ такая процедура невозможна, так как программа на АЛГОЛе не может генерировать другую программу.)

Приближенное интегрирование

Рассматриваемая здесь задача состоит в вычислении определенного интеграла на некотором интервале с соблюдением заданной точности; интервал делится на части, и формула

квадратуры применяется по очереди к каждому подинтервалу. Точность приближения контролируется путем применения формулы интегрирования к заданному интервалу с последующим делением интервала пополам, после чего формула интегрирования применяется по очереди к каждой половине интервала и полученные два результата складываются. Таким образом, если G(a, &,f)—функция, являющаяся приближенным значением

ь

J f(x)dx а

И МЫ ХОТИМ ВЫЧИСЛИТЬ

У

J F (х) dx х

то мы вычисляем G(X, У, F\ G(X, Z, F) и G(Z, У, F\ где Z=I/2(X + y). Если разность

G(Z, Z, F) + G(Z, У, F) —G(X, У, F)

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

S^x, У, f) = Mod((G(x, ^(х + у), f) + GC/2(x + y)» У, 0-

-GU, у. ^О^х, У. №

Цх, У. f^[S^ у, f)<D^G(xt у, П»

Цх, Ч^Ц + уХ f) + /(72U + у\ у» f)l

Здесь D — максимальная допустимая ошибка; значение функции I(x,y,f) является значением

у

J dz

X с заданной точностью.

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

На АЛГОЛе программа интегрирования принимает следующий вид:

real procedure Цх, у, f)-,

value х, у; real х, у; real procedure f;

begin comment предполагается наличие процедуры Gauss (а, b, g) для вычисления интеграла g(z)dz в интервале от а до b по формуле квадратуры’,

real G; G: = Gauss (х, у, f);

begin real procedure S(a, b, f);

value a, b; real a, b; real procedure f;

begin real z, c\

c: = <0+^12;

S: = abs ((Gauss (a, c, f) — Gauss (c, b, f) — Oyoy, end;

if S(x, у, П< ho — 5 then I: = G

else 1: = 1 (x, (x + t/)/2, /)

+ 7((х+у)/2, У, f)

end;

end;

Теория чисел

Мы приводим два примера из области теории чисел: вычисление простых множителей и отыскание разбиений.

. Простые множители. Алгоритм разложения целого числа N на простые множители является очевидным:

Если N — четное, то один из множителей равен двум; применяем тот же процесс к значению NJ2.

Если N делится на 3, исключаем этот множитель и повторяем тот же процесс для оставшегося значения 7V/3.

Если N делится на 5, исключаем этот множитель и при' меняем тот же процесс к оставшемуся значению NJ5.

Могло бы показаться, что необходимо выполнять шаги вида (2) и (3), используя только простые числа. На самом деле можно повторять процесс, перебирая нечетные числа, поскольку, например, кажущийся множитель 9 к моменту соответствующей проверки уже будет исключен как 3X3. Приведем теперь рекурсивную программу, реализующую этот алгоритм. Предположим, что результатом применения функции СПМ (п) является список простых множителей числа п, например:

СПМ (42) = (2, 3, 7)

Предположим также, что предусмотрены функция Cons(х, у), которая добавляет элемент х к списку у^ и функция Список^К

которая организует список, состоящий из одного элемента х. Тогда

CnM^n^Vf.OcT^ 2) = 0-+Cons(2, СПМ№^ ПМЦп, 3)] где ПМЦп, т) = [(п= 1)-> ПУСТО, - (п < т^ -> Спас ок (п\ Ост^, m) = 0->Cons(m1 ПМ\(п!т, т^, ПМЦп, т + 2)]

Например:

СПМ (330)== (2, СПМ(165)) = (2, ПМЦ165, 3)) = (2, 3, ПМЦ55, 3)) = (2, 3, ПМЛ (55, 5)) = (2, 3, 5, ПМЦП, 5)) = (2, 3, 5, 11)

Разбиения. Разбиениями целого числа п называются способы представления числа п в виде суммы целых чисел. Например, разбиениями числа 5 являются

4+1, 3 + 2, 3+1 + 1, 2 + 2+1, 2 + 1 + 1 + 1,

1+1+1+1+1

Представляет интерес подсчет числа различных разбиений произвольного целого п. Для этого удобно воспользоваться функцией <7mn, значением которой является число способов представления целого т в виде суммы, при условии, что каждое слагаемое не превосходит п. Число разбиений целого N равно qNN. Значение qmn может быть определено следующим образом. Имеем qVn =1для всех п

qma = IДля /всех т

Ят, п == Ят, т> ССЛИ Ш <С П

Ят, т == 1 + Ят, m—1

Ят, п == Ят, n—1 + Ят—n, т ССЛИ Ш, > П

Эти соотношения объединяются в следующем рекурсивном определении:

qm,n = \km= 1) V (П= 1)-И, (т</г)^ 1 + qm,m-v, (,qm, n—1 ~Н qm—n, га)]

’) Oct (n, m) —остаток от деления п на т; ПУСТО — пустой список.— Прим, перев.

Легко написать соответствующую рекурсивную процедуру на АЛГОЛе:

integer procedure q^m, п.у, value m, n; integer m, n; begin q: = if m = 1 V л = 1 then 1 else

if m ^ n then 1 + q^m, m— 1)

else (<7(m, n — 1) + q^m — n, n))1

end;

. В процессе такого вычисления q(m,n) некоторые другие значения q будут вычисляться многократно, что приводит к неэффективности. Можно написать нерекурсивную процедуру вычисления q^m, п^ симметричным способом:

integer procedure q^m» п); value т, п\ integer m, п;

begin integer k, Z; integer array Q[(1 мп\ (1 :n)];

for k: = 1 step 1 until m do

begin for Z: = 1 step 1 until n do

Q\k, Z]: = if k = 1 V I = 1 then 1 else if k^l then 1+Q[^> I— 1]

•else ^QYk» Z —1] + Q[£ —Z, Z])

end;.

q : = Q[m, n\ end;

В процессе вычисления qmn по этой процедуре ни одно значение q не вычисляется более чем один раз. Однако некоторые значения q вычисляются без надобности, хотя в отдельных случаях и неочевидно, сколько получается ненужных значений q.

Приведем теперь программу на языке ЛИСП (заимствованную у Маккарти). Эта программа организует таблицу значений q и вычисляет только те значения, которые действительно нужны. Читателям, совсем незнакомым с языком ЛИСП, следует пропустить дальнейшую часть п. 2.1.4.

Программа состоит из нескольких описаний функций. В ней используется список „известные", в котором перечисляются все уже вычисленные значения q. Этот список имеет вид

((m, п, qmn) ...)

Вот описания функций:'

присутствие [/та; п; известные] = ~null [известные]

A[[eq[caar [известные]; т] Д eq [cadar [известные]; та]] ■V присутствие [m; п; cdr

"[известные]]]

Эта функция принимает значение true, если qmn содержится в списке „известные", и значение false, если qmn отсутствует в списке или если список не существует. Описание является достаточно очевидным.

знач [т; п} известные] = [eq [сааг [известные]} пг]

/\ eq [cadar [известные]} п]->

,—> caddar [известные]}

Т~>знач[т} п; cdr[u3eecTHbte]]]

Эта функция дает значение qmn из списка; данное описание тоже не содержит неясностей.

ЛИ= cons [список [пг} п} и]; известные]

Эта функция добавляет к списку „известные" новый элемент. Заметим, что в этом определении т, п и известные — свободные переменные.

f2 [г] = знач [пг — п} п} г] + знач [пг} п — 1; 2]

Эта функция строит новое значение q по двум значениям q, содержащимся в списке.

след[т} П} известные]

Эта функция служит для получения нового списка „известные", который включает значение qm>n и все другие значения q, появившиеся в процессе вычисления qmn и не внесенные ранее в список „известные".

Легко получаем описание функции:

след[пг} п} известные]

= [присутствие[пг} п} известные]-> известные}

Т—> f 1 [[пг = 1 V п= 1 V m=^-> 1;

пг ^ п -> 1 + знач [пг} пг — 1; след [пг} пг — 1;

известные]}

T->f2 [след [пг} п — 1; след [пг — п} П} известные]]]]]]

Если qmn содержится в списке, то эта функция ничего не изменяет. Если qmn отсутствует в списке, то происходит обращение к функции fl, которая добавляет новый элемент к списку известных значений. Аргументом функции fl является значение qmn, и поэтому аргумент для fl выражается в соответствии с исходным описанием qmn с той разницей, что, когда требуется какое- то значение q^, пишется функция

знач [Z; /; след [Z; /; известные]]

Наличие третьего аргумента след [Z; /; известные] означает, что значение qtj будет вычисляться только в том случае, если его

еще нет в списке «известные». Окончательно получаем формулуq\m\ п\ = знач [т; п; след [т; п; ПУС7‘О]]

Процесс начинается с применения этой формулы при пустом списке «известные».

Другие примеры из численного анализа

Вычисление кратных интегралов уже рассматривалось в гл. 1. Аналогичная ситуация возникает при вычислении полиномов от нескольких переменных. Полином от п переменных Xi, х2, ..., хп может быть представлен как полином от хп, коэффициенты которого в свою очередь являются полиномами от (я — 1) переменных хь х2, ..., хп-ь Коэффициенты этих полиномов являются полиномами от (п—-2) переменных xi,x2,... ,хп-2 и т. д. Процедура вычисления такого полинома является рекурсивной по существу, так как процесс вычисления коэффициентов полинома включает вычисление других полиномов.

На этом этапе целесообразно упомянуть также получение перестановок, хотя эта задача и не совсем относится к численному анализу. Все перестановки N объектов могут быть получены, если брать по очереди каждый объект и помещать его перед всеми перестановками оставшихся (^—1) объектов. Таким образом, можно описать перестановки какого-то набора объектов с помощью перестановок меньшего числа объектов. Другими словами, имеется возможность написать рекурсивную программу получения перестановок N элементов, которая явно выполняет перестановки при N = 2 и обращается к себе рекурсивно при N > 2. Этот пример еще раз иллюстрирует изящество рекурсивных описаний; любое нерекурсивное описание данного процесса оказалось бы гораздо более сложным.

Рекурсия в компиляторах

Написание компиляторов является областью широкого применения рекурсии. В сущности рекурсия в настоящее время является для разработчиков компиляторов стандартным приемом. Известно много примеров использования рекурсии в компиляторах. Мы приведем здесь лишь несколько примеров, чтобы пояснить применяемые методы.

Условные операторы

Предположим, что в языке, состоящем из командных операторов, предусмотрена конструкция

ЕСЛИ В, SI, S2

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

Переход на Ы, если не В

S1

Переход на L2

Ы: S2 L2: ...

Компилятор, прочитав строку, начинающуюся со слова ЕСЛИ, вызвал бы подпрограмму со следующей спецификацией:

Компилировать код для вычисления условия не В Завести новую метку L\ Компилировать „Переход на Ы, если истина" Компилировать оператор 31 Завести метку L2

Компилировать „Переход на L2

LV."

Компилировать оператор 32

Компилировать „L2*." Выход

Теперь предположим, что мы хотим уметь обрабатывать вложенные условия:

ЕСЛИ В1, ЕСЛИ В2, 31, 32, S3

илиЕСЛИ В1, 31, ЕСЛИ В2, 32, S3

(эти условия означают

ЕСЛИ В1, {ЕСЛИ В2, SI, S2), S3

и ЕСЛИ Bl, S1, {ЕСЛИ В2, S2, S3) соответственно).

Мы можем достичь этой цели, написав рекурсивную подпрограмму под названием COMPILE, результатом выполнения которой является компиляция одного оператора. Вот ее спецификация:

COMPILE*. Если оператор начинается с „ЕСЛИ", то переход на LL

Компилировать оператор {до запятой или до конца строки)

Выход

LL;Читать условие {до запятой)

Компилировать код для вычисления обратного условия

Завести метки L\, L2

Компилировать „Переход на Li, если истина" Обратиться к COMPILE

Компилировать „Переход на L2

L1"

Обратиться к COMPILE Компилировать „L2." Выход

В случае простого условного оператора эта программа действует точно так же, как предыдущая. Но если задан оператор

ЕСЛИ 51, ЕСЛИ В2, SI, S2, S3

то после компиляции кода для условия произойдет рекурсивное обращение к COMPILE, при которой обнаружится второе слово ЕСЛИ и начнется компиляция внутреннего условного оператора ЕСЛИ B2t SI, S2. После завершения этой работы произойдет возврат к предыдущему выполнению подпрограммы COMPILE и будет закончена компиляция оставшейся части внешнего оператора ЕСЛИ. При рекурсивном обращении будут заведены новые метки для внутреннего оператора ЕСЛИ; в результате получится код следующего вида:

Переход на Li, если не 51

Переход на L3, если не В2

S1

Переход на L4

L3: S2

L4: Переход на L2

Li: S3

L2: ...

Можно обобщить эту схему так, чтобы допускались составные операторы. Теперь задача состоит в том, чтобы можно было заменять S1 в операторе ЕСЛИ на

(SI, S2, S3, ..., Sn)

Например, запись

ЕСЛИ 51, (SI, S2), (S3, S4, S5)

после компиляции была бы переведена в такой вид:

Переход на Li, если не 51

S1

S2

Переход на L2

Li: S3

S4

S5

L2;.

Для этого мы модифицируем подпрограмму COMPILE следующим образом:

COMPILE; Если оператор начинается с „(“, то переход на LX Если оператор начинается с „ЕСЛИ", то переход на LL

Компилировать оператор до запятой или до „)“ или до конца строки

Если встретилась запятая или кончилась строка, то установить Sw = 0, в противном случае установить Sty = 1

Выход

LX:Обратиться к CSCOMP

Выход

LL:Как ранее

CSCOMP — это рекурсивная подпрограмма со следующей структурой:

CSCOMP: Обратиться к COMPILE

Если Sty = 0, го переход на CSCOMP, в противном случае Выход.

Таким образом, если при чтении встретилась открывающая скобка, то управление «перехватывается» программой CSCOMP до тех пор, пока не встретится соответствующая закрывающая скобка. (Заметим, что программа CSCOMP является косвенно рекурсивной, так как она обращается к программе COMPILE, которая может в свою очередь обратиться к CSCOMP.)

Если на входе задан оператор

ЕСЛИ В, (SI, S2), S3

то после рекурсивного обращения к COMPILE для обработки первого ответвления выход из программы COMPILE не произойдет до тех пор, пока не встретится соответствующая закрывающая скобка. Итак, сравнительно простая рекурсивная подпрограмма справится с обработкой сколь угодно сложной суперпозиции условных и составных операторов1).

Синтаксический анализ

Во многих случаях синтаксис языка имеет рекурсивную структуру. Например, в английской грамматике именная группа

может быть определена как

the {существительное)

илиthe {прилагательное) {существительное)

или{именная группа) {именная группа) {глагол)

Таким образом, обе конструкции «the pink elephant» и «the pink elephant the man sees» являются именными группами1). Мы замечаем, что третий вариант в приведенных выше определениях описывает именную группу через самое себя. Метод рекурсивного описания может успешно применяться и к синтаксису языка программирования. Общеизвестным примером является формальное описание языка АЛГОЛ-60 [2], которое дано в записи, получившей известность под названием нормальной формы Бэкуса. Эта форма описания применима к широкому классу искусственных языков, известному под названием «языки непосредственных составляющих» (см. [3]). Проиллюстрируем это на примере описания десятичного числа. Запись.

{цифра):: = 0\\ |2 |3 |4 |5 |6 |7 |8 |9

определяет класс {цифра) как состоящий из вариантов 0,1,2,...,9. (Символ ::= можно читать как «определяется как», вертикальную черту можно читать как «или»). Теперь можно определить более сложные конструкции.

{целое без знака) :: = {цифра) | {целое без знака) {цифра)

Это рекурсивное описание целых чисел. Например, 123 — целое без знака 12, за которым следует цифра 3; 12 — целое без знака 1, за которым следует цифра 2; 1 — цифра.

{правильная дробь) :: = •{целое без знака) {десятичное число) :: = {целое без знака) \{правильная дробь) | {целое без знака) {правильная дробь)

Другое возможное определение целого без знака могло бы быть таким:

{целое без знака) :: = {цифра) \ {цифра) \{целое без знака)

Это определение формально эквивалентно предыдущему. На практике алгоритм, применяемый для синтаксического анализа, обычно предопределяет выбор способа записи рекурсивных описаний. Более сложным примером является описание арифметических выражений.

Мы определяем простое арифметическое выражение (ПАВ) с помощью следующих конструкций:

(отс) :: = + I —

(оту) :: = X I/

{первичное) :: = {целое без знака) \{переменная) \({ПАВ)) {терм) :: = {первичное) \ {терм) {оту) {первичное) {ПАВ) :: — {терм) | {отс) {терм) | {ПАВ) {отс) {терм)

При компиляции возникает проблема распознавания класса, к которому принадлежит данная строка символов. Например, строка

A + <C-D)XB

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

А переменная !1

+ отс 1 1

( С-

переменная отс 11 1 1

D ) переменная

X оту 1!

В переменная 11

первичное 1I

первичное

I1

первичное

I1

терм 1!

терм !I

терм 11

ПАВ 1!

ПАВ 1

1

первичное

11

терм

1

1

первичное

11

ПАВ 1I

терм

1

ПАВ

Так как

синтаксис описывается

рекурсивно,

то

неудивитель-

но, что рекурсивный метод хорошо подходит для такого вида

анализа.

Метод, который будет сейчас описан, в основном базируется на «Диаграмме» Айронса [4], хотя существуют и другие программы синтаксического анализа, работающие аналогичным способом (например, см. [5]). «Диаграмма» представляет собой процедуру, при входе в которую задаются указатель для исходной строки и определенная «цель». «Целью» является какой-то

синтаксический класс. Если символы, непосредственно следующие за указателем, образуют пример из этого класса, то результатом является ответ «истина» и указатель продвигается вперед; в противном случае результатом является ответ «ложь» и указатель остается в своем прежнем положении. Этапы анализа приведенного выше выражения показаны на рис. 2.1.

А + (С - D) х вЦель: ПАВ

ПАВ может быть термом:

А + (С — D) X В Цель: терм

Терм может быть первичным

А + (С — £)) X В Цель: первичное

„А“ является примером из класса „переменная"; первичное может быть переменной, поэтому получаем результат ИСТИНА

ИСТИНА „терм" найден

ИСТИНА „ПАВ" найдено

Можем ли мы найти большую строку, которая также является

ПАВ? Пытаемся применить конструкцию (ПАВ) :: = (ПАВ) (отс) (терм)

+ (С — D) X В Цель: отс

ИСТИНА

(С — D) X В Цель: терм

t

Терм может быть первичным; „(“ может служить началом первичного, поэтому пытаемся применить конструкцию (первичное):: = ((ПАВ))

С — D) X В Цель: ПАВ

„С" является примером из класса „переменная"; первичное может быть переменной, поэтому получаем результат ИСТИНА

Можем ли мы найти большую строку, которая также является ПАВ?

Пытаемся применить конструкцию (ПАВ):: = (ПАВ) (отс) (терм)

— D) X В Цель: отс

ИСТИНА

D) X В Цель: терм

„0“ является примером из класса „переменная"; переменная является первичным и термом, поэтому получаем результат ИСТИНА

ИСТИНА „ПАВи найдено

Можем ли мы найти большую строку, которая также является ПАВ?

) X В Цель: отс

t

ЛОЖЬ

Самое большое ПАВ найдено

) X В Цель: „)"

t

ИСТИНА

ИСТИНА „первичное" найдено, поэтому „терм" найден

Можем ли мы найти больший терм?

Единственной возможной конструкцией является („терж") (огр) (первичное)

X В Цель: оту-

ИСТИНА

В Цель: первичное

„В" — это переменная, а следовательно, первичное, поэтому получаем результат

ИСТИНА-

ИСТИНА ПАВ найдено, и выражение полностью проанализировано.

Рис. 2.1. Работа «Диаграммы».

На этом рисунке каждый отступ текста представляет рекурсивный вход в «Диаграмму», причем для каждого входа справа показана входная строка.

Можно представить этот анализ в виде очень короткой программы, так как он сводится к простому процессу распознавания, применяемому с большой глубиной рекурсии. Дальнейшие подробности можно найти в статье Айронса [4]. Это очень хороший пример эффективности рекурсивной процедуры. Однако он может служить также иллюстрацией возможной расточительности при необдуманном применении рекурсии. Например, в языке АЛГОЛ-60 идентификатор определяется так:

{идентификатор}:: = {буква} \ {идентификатор} {буква} |{идентификатор} {цифра}

Это определение означает, что идентификатор состоит из одного или более символов, из которых первый должен быть буквой, а остальные могут быть буквами или цифрами. Если задано это синтаксическое определение, то «Диаграмма» будет правильно опознавать идентификаторы, но при этом возникнут большие потери при использовании процедуры рекурсивного определения для задачи опознавания, которая может быть решена простым прямым просмотром. На практике перед синтаксическим анализом следует выполнять лексический анализ. На этапе лексического анализа такие синтаксические объекты, как идентификаторы, числа и разделители, опознаются при прямом просмотре и передаются для синтаксического анализа как законченные величины. Аналогично, арифметические выражения, удовлетворяющие некоторым правилам, также могут анализироваться прямым просмотром (см. разд. 2.4, а также работу Флойда [10])'. Если для заданного языка эти правила выполняются, то можно добиться значительного выигрыша, включив в синтаксис единое

понятие «строка операция — операнд»; после опознавания таких строк к ним применяется отдельная процедура анализа. Не следует автоматически считать преимуществом применение рекурсии, если та же задача может быть решена нерекурсивно.

Сортировка

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

От корня дерева в каждую вершину проходит единственный путь. При сортировке по дереву элементы размещаются на вершинах дерева таким образом, чтобы на любом пути из какой- либо вершины по левой ветви встречались только такие элементы, у которых значения ключа меньше, чем значение ключа для данной вершины. И наоборот, любой путь из какой-либо вершины по правой ветви приводит только к таким элементам, у которых значения ключа больше, чем значение ключа для данной вершины.

На языке ЛИСП программа выполнения сортировки может быть составлена следующим образом. Предполагаем, что подлежащие сортировке объекты представляют собой списки, причем в каждом списке первым элементом является ключ. На вход программы подается список этих списков, т. е.

((ключ 1, .♦.), (ключ 2, ...), ..., (ключ п, ...))

Требуется построить список из тех же списков так, чтобы в нем ключи следовали в порядке возрастания их значений. Сначала определим функцию добав с двумя аргументами. Одним аргументом является элемент х, другим — частично построенное дерево 2. Значением функции является дерево, получаемое путем.

добавления элемента х к дереву 2. Дерево состоит из вершин, каждая из которых представляет список из трех элементов:

Итак, если w— вершина, то ключ элемента из этой вершины определяется по формуле caar (w), левая ветвь — это cadr (w), правая ветвь — это caddr (w). Функция добав описывается следующим образом:

добав [х; 2] = [null [2] -> список, [х; ПУСТО; ПУСТО];

. car[x] < сааг [2] ~>

список[саг [2]; добав [х; cadr [2]]; caddr[2]];

Т-> список[саг[г]; cadr [2]; добав [х; caddr [2]]]]

Далее определим функцию construct [ш; у], которая добавляет все элементы списка w к дереву и; здесь w— список списков, аналогичный описанному ранее.

construct [ш; v] = [nulZ[w]->v;

Т -> construct [cdr[w]; добав [car [w]; у]]]

Это формальное описание означает, что мы добавляем первый элемент списка w к дереву у, а затем применяем функцию construct к оставшейся части списка и к новому дереву. Если исходный (неупорядоченный) список называется вхсписок, то, применив функцию

construct [вхсписок; ПУСТО]

мы получим дерево упорядочивания элементов списка вхсписок. Заключительный этап состоит в получении линейного упорядоченного списка. Это выполняется с помощью функции лин [а; 6], определяемой следующим образом:

лин[а; b] = [nuZl[a]->b;

Т -> Aun[cadr[a]; cons [саг [а];лин [caddr [а]; 6]]]]

В этом описании а — дерево, b— конструируемый линейный список. Если функция null (а) принимает значение «истина» (что соответствует отсутствию ответвления от вершины), то список b не изменяется, в противном случае результат выравнивания ле-

вой ветви добавляется к списку, полученному добавлением элемента из данной вершины к результату добавления выровненной правой ветви к списку Ь. Этот процесс начинается при пустом списке 6, т. е. выполняется оператор

лин\1; ПУСТО]

где / — дерево. Дерево преобразуется в упорядоченный список с помощью функции

лин\1; ПУСТО]

Полное выполнение сортировки обеспечивается применением функции

8ог1\вхсписок\ = лин\соп81гис1\вхсписок\ ПУСТО]; ПУСТО]

Обработка алгебраических выражений

Рекурсия широко применяется при обработке символов. В качестве примера мы рассмотрим здесь обработку алгебраических .выражений. Эти выражения состоят из наименований переменных, а также из знаков операций и скобок. Мы будем обозначать переменные одиночными буквами. Вот примеры алгебраических выражений:

A + B + C*D

A + (B + C)*D

((А*В)* D —F)/(G + Н)'

Такие выражения имеют рекурсивную структуру, поскольку все операции, кроме одноместного минуса, применяются к двум операндам. Поэтому выражение можно описать так:

операнд операция операнд

Здесь операнды либо являются переменными, либо в свою очередь представляют собой выражения. Рекурсивная структура становится более очевидной, если писать операции перед операндами. Например, выражение

A-VB-VC*D

в таком случае приобретает вид ПЛЮС (Л, ПЛЮС (5, УМНОЖИТЬ (С, D^)

В обычной записи алгебраических выражений подразумевается старшинство операций умножения по сравнению со сложением. Запись с вынесенными вперед операциями в точности соответствует полной скобочной записи:

(Л+5 + (С*/))))

Если требуется обрабатывать такие выражения, то выгодно выбрать представление в машинной памяти, которое отражает

рекурсивность структуры. Одно из таких представлений сводится к применению списков: выражение представляется в виде списка из трех элементов, соответствующих операции и двум ее операндам. Если операнды являются выражениями, то они представляются как подсписки. Таким образом, выражение

Л+ (5 + C)*Z)

представляется списком

{ПЛЮС, А, {УМНОЖИТЬ, {ПЛЮС, В, С), D))

а выражение

{{А*ВИ D — P^G + H)

представляется списком

{РАЗДЕЛИТЬ, {МИНУС, {СТЕПЕНЬ, {УМНОЖИТЬ, А, В), D> Р\ {ПЛЮС, G, Н))

Предположим, что теперь мы хотим продифференцировать такое выражение. Заметим, что операция дифференцирования является рекурсивной, поскольку

4-^a-Vb^=4-(aH4-Wdx х 17 dx х 7 1 dx х 7

-4—{и и) = и + у*-т~(ц)dx х 7 dx х 7 1 dx х 7

Если предположить на время, что единственными операциями являются + и *, то программа дифференцирования становится очень простой. Следующая функция на языке ЛИСП порождает производную от выражения е относительно переменной х:

^7f lA Х1= [atom Iе] А еЧ [^> Х1 1»

eq [саг [е]; ПЛЮС\-> список [ПЛЮС*, diff [cadr [е]]; diff [caddr [е]]];

eq[car[eY УМНОЖУ

список [ПЛЮС*, список[УМНОЖ; cadr[e]; diff [caddr [еЦ; список [УМНОЖ; diff [cadr [е]]; caddr [е]]]]

Очевидно, что легко обобщить эту программу так, чтобы она обрабатывала и другие операции.

Так как полная скобочная форма арифметического выражения имеет простую рекурсивную структуру, то она может быть преобразована в форму с вынесенными вперед операциями следующим образом. Описываем две рекурсивные подпрограммы OPERATOR и OPERAND.

OPERATOR*. Если очередной символ не является + , —, X или /, то записать ОШИБКА*, в противном

случае выдать в качестве результата очередной символ и продвинуть на один шаг указатель во входной строке.

OPERAND: Если очередной символ (элемент) является наименованием переменной, то выдать его в качестве результата. В противном случае, если очередной символ не „(“, то записать ОШИБКА*, если „(и, то

Вызвать OPERAND: обозначить результат через Rx

Вызвать OPERATOR: обозначить результат через R2

Вызвать OPERAND: обозначить результат через R3

Построить список (R2, Rx, R3)

Если следующий символ „У^ то выйти из подпрограммы с выдачей полученного списка в качестве результата, в противном случае записать ОШИБКА.

Если все выражение заключено в скобки, то одно обращение к подпрограмме OPERAND приведет к получению результата, представляющего собой список в форме с вынесенными вперед операциями. Программа такого типа описана в работе [6]. Однако полная скобочная запись выражений обычно не применяется. Поэтому мы опишем теперь способ, который пригоден и для бесскобочных выражений.

Представление выражения в виде списковой структуры является, по сути дела, «прямой польской записью», в которой операция записывается перед своими операндами, т. е.

А + В* С записывается в виде + А*ВС

и(А + В)* С записывается в виде * + АВС

Дийкстра [7] предложил простой способ преобразования выражения в «обратную польскую запись» за один последовательный просмотр. Каждой операции ставится в соответствие некоторый приоритет, а именно:

+ , -2

*, /3

t4

(Эти приоритеты отражают старшинство операций умножения и деления по сравнению со сложением и вычитанием и старшинство возведения в степень по сравнению со всеми остальными операциями.) Алгоритм преобразования основан на использовании стека и состоит в следующем:‘

Проверяется очередной символ во входной строке.

Если это операнд, то он передается в выходную строку.

Если это открывающая скобка, то она заносится в стек с приоритетом нуль.

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

Если текущий символ во входной строке является закрывающей скобкой, то операции из стека последовательно переносятся в выходную строку до тех пор, пока на вершине стека не появится открывающая скобка; эта открывающая скобка отбрасывается.

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

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

Л + В*С + (/) + £)*^

Входная строка

Выходная строка

Стек (вершина стека справа)

А + В*С 4- Ф 4- EY F

пустая

пустой

4- В*С + (D + ЕУ F

А

пустой

В*С А- ф + ЕУ F

А

4-

*С + (D 4- Е)* F

АВ

+

C + (D + E)*F

АВ

4-*

+ (D + E)*F

АВС

4-*

(D + E)*F

АВС* +

+

D 4- E)* F

АВС* +

+ (

-4- E)* F

АВС* 4- D

+ (

E^F

АВС* 4- D

+ (4-

У F

АВС* 4- DE

+ (+

* p

АВС* 4- ЕЕ 4-

+

F

АВС* + DE +

4-*

пустая

АВС* + DE + F

4-*

АВС* 4- DE 4- F* 4-

пустой

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

Опишем подпрограмму «Получение операнда» со следующей спецификацией:

Если очередной элемент во входной строке является наименованием переменной, то он выдастся в качестве операнда и указатель во входной строке продвигается вперед. В противном случае очередной элемент должен оказаться операцией. Организуется список из трех элементов, операция заносится в первый элемент списка, и указатель во входной строке продвигается. Затем два раза выполняется «Получение операнда», и полученные два операнда заносятся в список.

Таким образом, если задана входная строка

*-V АВС

то подпрограмма «Получение операнда» работает так:

Организуется список (*, ПУСТО, ПУСТО). ,

Производится обращение к «Получению операнда». Следующий элемент является операцией, поэтому организуется список (+, ПУСТО, ПУСТО). Обращение к «Получению операнда». Следующий элемент — это А, поэтому он заносится в качестве операнда для +, получаем (+, А, ПУСТО). Снова обращение к «Получению операнда», в результате имеем (+, А, В).

Теперь производится возврат на предыдущий уровень рекурсии с получением первого операнда для *; в результате имеем (*, (+, Л, В), ПУСТО).

Обращение к «Получению операнда» за вторым операндом для *; в результате имеем (*, (+, Л, В), С).

Опять мы имеем дело с очень простой рекурсивной подпрограммой; эта простота является, разумеется, следствием рекурсивной структуры, выбранной нами для представления выражений.

2.5. Системы решения проблем

Рекурсивные методы играют большую роль в системах, предназначенных для моделирования человеческого мышления, т. е. в области, которую иногда называют «искусственным

интеллектом». Для иллюстрации этого утверждения мы рассмотрим здесь в качестве примера «Универсальный решатель задач», авторами которого являются Ньюэл, Шоу и Саймон [8]. С другими примерами можно ознакомиться по книге [9].

Общая программа решения проблем, которую мы будем называть далее GPS (сокращение английского названия «General Problem Solver»), представляет собой пример эвристической программы. Это означает, что GPS в процессе своей работы пытается найти нужный подход к решению проблемы путем пробного применения многих различных методов и сравнения получаемых при этом результатов. Вообще говоря, если задана цель, которую нужно достигнуть, то GPS разлагает ее на подцели и сначала пытается достичь отдельных подцелей. Процесс достижения какой-то подцели может включать дальнейшее подразделение, так что нам видна существенно рекурсивная структура этой системы: подпроцессы идентичны основному процессу, частями которого они являются. Система GPS оперирует символьными объектами, с помощью которых описываются или характеризуются ситуации. Эта система работает также с символами, представляющими различие между парами объектов, и с символами, представляющими операторы, которые применяются к объектам и могут вызывать изменения в этих объектах.

Система GPS может выполнять процессы, связанные с достижением целей трех типов:,

Преобразование*. преобразовать объект а в объект Ь.

Сокращение различия*, уменьшить или исключить различие между объектами а и Ь.

Применение оператора*, применить оператор q к объекту а.

Эти процессы рекурсивно взаимосвязаны. Процесс преобразования объекта а в объект b состоит в следующем:

Установить различие d между а и Ь.

Подцель: уменьшить d.

Попытаться достичь подцели, в случае успеха найти новое различие и, если оно не нуль, повторить тот же процесс.

Процесс сокращения различия d состоит в следующем:

Найти оператор q, который подходит для различий типа d.

Подцель: применить q к d.

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

Список литературы,Список литературы,45

Список литературы,

Список литературы,

Процесс применения оператора q к различию d состоит а следующем:

Проверить выполнение условий применимости q к d.

Если условия выполняются, то применить q; в противном случае

Подцель: преобразовать d в такой объект, который удовлетворяет условиям.

В случае успеха применить q.

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

Очевидно, что такая совсем простая проблема, как доказательство тождества

sin2 х + cos2 х = tg х • ctg x

приведет к сложному рекурсивному переплетению описанных процессов, и было бы немыслимо применять GPS без использования рекурсии.

СПИСОК ЛИТЕРАТУРЫ

McCarthy J., Memorandum 32, Artificial Intelligence Project, MIT Computation Center.

Naur P. (ed.), Revised report on the algorithmic language ALGOL 60, Commun. Assoc. Computing Machinery, 6, № 1 (1963), 1; Computer J., 5, № 4 (1963), 349. (Русский перевод: Наур П. (под ред.), Алгоритмический язык АЛГОЛ-60, Пересмотренное сообщение, «Мир», М., 1965.)

Chomsky A. N., On certain formal properties of grammars, Information and Control, 2 (1959), 137. (Русский перевод: Хомский А., О некоторых формальных свойствах грамматик, Кибернетический сборник, вып. 5, ИЛ, 1962, 279—312.)

Irons Е. Т., The structure and use of the syntax directed compiler, Ann. Rev. Automatic Programming, v. 4, p. 207, ed. R. Goodman, Pergamon, 1963.

Brooker R. A., et al, The compiler-compiler, Ann. Rev. Automatic Programming, 4, p. 229. Ed. R. Goodman, Pergamon, 1963.

Barron D. W., Strachey C., Programming: ch. 2 of «Advances in programming and non-numerical computation», ed. L. Fox, Pergamon, 1966.

Dijkstra E. W., Making an ALGOL translator for the XL Reprinted, in Annu. Rev. Automatic Programming, v. 4, ed. R. Goodman, Pergamon, 1963.

Newell A., Shaw C. J., Simon H. A., Report on a general problem solving program, in Information processing, Proceedings of the UNESCO Conference, Paris, 1959, p. 256, UNESCO (Paris), 1960.

Feigenbaum E. A., Feldman J. (ed.), Computers and thought, McGraw-Hill, 1964.

Floyd R. W., On syntax analysis and operator precedence. Report CA-62-2, Massachusetts Computer Associates, 1962.

СРЕДСТВА РЕАЛИЗАЦИИ РЕКУРСИИ

Постановка задачи

Реализация рекурсивных процедур сводится в основном к проблеме работы с подпрограммой, содержащей обращение к самой себе. Это означает, что каждому новому обращению к такой подпрограмме должны соответствовать другой набор рабочих регистров и другое место |В памяти для запоминания адреса возврата. При входе в подпрограмму нужно отводить для нее новый набор рабочих регистров, а при выходе, прежде чем передавать управление по адресу возврата, следует восстанавливать то состояние рабочих регистров и других ресурсов, которое существовало к моменту соответствующего обращения к подпрограмме. Эти операции выполняются автоматически при «встроенных» рекурсивных системах, однако их приходится программировать явно, если рекурсия реализуется с помощью системы подпрограмм или с помощью метода макропрограммирования. Может оказаться также, что рекурсия реализуется с помощью специальной аппаратуры, но, с точки зрения программиста, нет существенной разницы между аппаратной реализацией и «встроенным» программным обеспечением; и в том и в другом случаях он может программировать рекурсивно, не уделяя никакого внимания проблемам запоминания и восстановления рабочих ячеек, ссылок и т. д.

Специальные методы

Рассмотрим в качестве типичного примера вычисление определенного интеграла. Соответствующая программа обычно получает три элемента начальных данных: верхний и нижний пределы интегрирования и адрес той подпрограммы, которая вычисляет подынтегральную функцию. Эта последняя подпрограмма часто называется вспомогательной подпрограммой и обычно выбирает из сумматора то значение аргумента, для которого требуется вычислить функцию; при выходе из этой подпрограммы значение функции для данного аргумента остается на сумматоре. Для подпрограммы интегрирования потребуются

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

Самое грубое решение этой проблемы состоит в том, чтобы хранить в памяти две различные копии подпрограммы интегрирования. Каждая копия пользуется своими собственными рабочими регистрами, и поскольку адреса возврата запоминаются отдельно для каждого варианта, то не может быть путаницы. Однако этот метод требует слишком большого расхода памяти и поэтому не применяется на практике. На следующем этапе усложнения метода память содержит только одну копию подпрограммы, но разные области рабочих ячеек и разные ссылки (адреса возврата). При этом подпрограмма имеет дополнительный входной параметр, являющийся адресом области рабочих ячеек (рабочего поля); адрес возврата запоминается на рабочем поле, и при всех обращениях из подпрограммы к ее рабочему полю используется индекс-регистр или косвенный адрес, который формируется по входному параметру. (Разумеется, это и есть метод «чистых процедур» или «реентерабельного кода», используемый в системах мультипрограммирования). Этот метод применим всякий раз, когда глубина рекурсии явно известна (и постоянна); он не годится, если глубина рекурсии не определена во время написания программы и становится известной только в процессе выполнения программы. На практике этот метод применяется только при малой глубине рекурсии.

Стеки

Почти все системы рекурсивного программирования основываются на идее стека (называемого иногда магазинной памятью или «нанизанной» памятью). Одно из самых ранних опубликованных описаний этого метода содержится в статье [1].

Магазинная память — это память, действующая по принципу LIFO1). Всякий раз, когда элемент информации заносится в такую память, мы говорим, что он поступает на вершину па-

*) Начальные буквы английского оборота «1ast-in-first-out», означающего «последним пришел — первым ушел». — Прим, перев.

мяти, «утапливая» все элементы, уже содержащиеся в памяти. Всякий раз, когда элемент выбирается из памяти, он берется с вершины и все оставшиеся элементы поднимаются вверх по стеку. Поэтому всегда первым удаляется именно тот элемент, который появился позже всех остальных имеющихся. Термин «стек» обычно применяется к такой структуре памяти, в которой, помимо доступа к верхнему элементу, имеется возможность обращаться к внутренним элементам. Более точно, стек — это память, работающая по магазинному1) принципу, поскольку дело касается добавления или удаления элементов, причем можно обращаться к любому из нижних элементов, ссылаясь на его положение относительно одного из нескольких указателей..

Рассмотрим сначала простой стек, в котором каждый элемент занимает одно слово машинной памяти. Стек состоит из некоторого числа последовательных регистров, а также из указателя стека S, который может храниться в регистре памяти или в индекс-регистре, в зависимости от конкретной машины. Указатель S всегда показывает очередную свободную ячейку в стеке. Пусть C[S] — содержимое ячейки, на которую указывает S (т. е. адрес которой содержится в S). Тогда существуют следующие основные операции над стеком:_

Поместить элемент А в стек: С[5]: = Л

S: = S+ 1

Извлечь элемент из стека:S: = S—1

A : = C[S]

Далее в этой главе стеки будут изображаться горизонтально, с ростом в правую сторону, таким образом:

4

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

*) Подразумевается аналогия с магазинным устройством огнестрельного оружия. — Прим, перев.

указателей, которые соответствуют элементам; например;

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

-11ШЗ|||||4|

।—। I। f

Элемент Элемент S

При этом основные операции над стеком приобретают следующий вид:

Добавить к стеку элемент

из п слов Л[1], .... Л[п]С[5]:==Л[1]

C[S + n—1]: = Л [п]

С [S + п]|: = п

S: = S 4- /г -[- 1

Извлечь элемент из стека:n':=C[S—1]

Л[п']: = С[3 —2]

Л[1] SЛ[1] S= C\S — n' — 1] = S — „'—1

Л[1] S

Л[1] S

Различные варианты этого метода описаны, например, в статьях [2, 3].

Основа для рекурсии

Мы можем теперь рассмотреть способ организации рекурсии па базе стека. Такая система включает стек, а также две подпрограммы, которые мы будем называть ОБРАЩЕНИЕ и ВОЗВРАТ.

Подпрограмма ОБРАЩЕНИЕ имеет три аргумента:

Адрес подпрограммы, в которую нужно войти.

Адрес первого регистра подлежащего запоминанию участка рабочего поля.

Число регистров, подлежащих запоминанию.

Работа подпрограммы ОБРАЩЕНИЕ состоит в том, чтобы запомнить в стеке адрес возврата и указанные регистры, а затем обычным образом передать управление на ту подпрограмму, к которой требуется обратиться.

Подпрограмма ВОЗВРАТ имеет два аргумента:

Адрес первого из подлежащих восстановлению регистров рабочего поля.

Число регистров, подлежащих восстановлению.

Работа подпрограммы ВОЗВРАТ состоит в том, чтобы восстановить по содержимому стека состояние указанных регистров, а затем передать управление по адресу возврата, который хранится в стеке.

Если ОБРАЩЕНИЕ и ВОЗВРАТ описаны как микрооперации, то подпрограмма вычисления факториальной функции, выбирающая аргумент из сумматора и помещающая результат в сумматор, имела бы следующий вид:

РАС, Перейти на ZERO, если сумматор содержит нуль Занести содержимое п сумматора в ячейку N Вычесть 1, занести п—1 в сумматор Рекурсивно обратиться к подпрограмме РАС с помощью оператора

ОБРАЩЕНИЕ FAC, N, 1

Умножить содержимое сумматора на содержимое ячейки N

Выйти по оператору ВОЗВРАТ, N, 1

ZERO, Занести в сумматор константу 1

Выйти по оператору ВОЗВРАТ, N, 1

Аналогичный прием для ФОРТРАНа описан Эйром [4]. Он несколько усложнен из-за того, что ФОРТРАН, как правило, не допускает обращения из подпрограммы к ней же самой и не предоставляет программисту доступа к связующей информации (адресу возврата). Нам понадобятся две подпрограммы, назы-

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

SUBROUTINE NFAC (N, NFACT, DUMMY)

IFW 3, 4, 6

CALL EXIT (6).

NFACT = 1

GO TO 11

CALL STORE (N)

N = N —1

CALL DUMMY (N, NFACT, DUMMY)

CALL RSTOR (N)

NFACT = NFACTN

RETURN

Параметр DUMMY служит для того, чтобы подпрограмма^ могла обращаться к себе самой. Из основной программы производится такое обращение:

' CALL NFAC (N, NFACT, NFAC)

и поэтому на время выполнения DUMMY заменяется на NFAC, и подпрограмма обращается к себе самой.

Подпрограмма STORE должна запомнить в стеке текущее значение N и связующую информацию; RSTOR должна восстановить эти данные по состоянию стека. Доступ из этих подпрограмм к связующей информации обеспечивается следующим приемом1), который его изобретатель сам расценивает как «беспринципную сделку». Если применяется стандартная процедура реакции на ошибки из системы ФОРТРАН/FAP (см. [5]), то обращение к подпрограмме дополняется следующими двумя словами:

NTR * + 2, 0, А

PZE С, 0, В

Первое слово соответствует обычному выходу из подпрограммы. Второе слово содержит связующую информацию: В — это адрес, откуда происходит обращение, С — адрес связующего звена в подпрограмме, содержащего адрес возврата. «Беспринципная сделка» состоит в том, что запись подпрограмм STORE и RSTOR предусматривает наличие трех аргументов N, NTR и LD, а обращение к подпрограмме производится только с одним

аргументом N. Поэтому обращение из подпрограммы к величине LD обеспечит доступ к связующему звену через дополнительные слова, добавленные к обращению.

Приводим теперь программы STORE и RSTOR

SUBROUTINE STORE (N, NTR, LD)

COMMON LIST

DIMENSION LIST (20)

L/Sr(l) = L/S7 (1)4- 1

I = LIST(\)

LIST(I) = LD

7ШТ(1) = £/5Г(1)+1■

I = LISTOV)

LIST (I) —N

RETURN

SUBROUTINE RSTOR (N, NTR, LD)

COMMON LIST

DIMENSION LIST (20)

I = LIST(\)

N = LIST (I)

LIST (Д) = LIST (Д) — 1

I = LIST (Д)‘

LD = LIST{I)

LIST (1) = LIST (\)— 1

RETURN

(В обеих программах выход осуществляется посредством TRA 4, 4, а не TRA 2, 4.)

Система IPL-V

Не обязательно, чтобы в системе был только один стек. Пожалуй, самая развитая организация работы со многими стеками используется в системе IPL-V [6]. В ней имеется один стек для связей подпрограмм, а также отдельные стеки, соответствующие каждой переменной. В системе обработки списков наименование переменной обозначает списковую структуру и обычно соответствует регистру, который содержит указатель на первый элемент этой структуры. В системе IPL-V наименование соответствует стеку, причем каждая ячейка из стека содержит указатель на списковую структуру или элемент числовых данных. В системе предусмотрены в качестве основных операций Запоминание («утапливание» в магазине) и Восстановление (выборка из магазина). От программиста требуется, чтобы он запоминал все нужные элементы, прежде чем обращаться к другой подпрограмме. Это правило не распространяется на одну

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

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

Обобщение понятия стека

Опишем теперь метод, с помощью которого сохранение параметров, зависящих от глубины рекурсии, может выполняться автоматически. В любой системе программирования существуют правила, относящиеся к способу обращения к подпрограммам, т. е. к способу передачи подпрограмме ее аргументов. Например, в системе FAP адреса аргументов появляются в регистрах, следующих за командой передачи управления на подпрограмму;

TSX SUB, 4

PZEаргумент 1

PZEаргумент 2

И т. д.

Приемлемой основой для рекурсии может служить соглашение, что подпрограммы берут свои аргументы из стека и оставляют в стеке любые результаты. Таким образом, если мы имеем подпрограмму с тремя аргументами X, У и Z, то последовательность обращения к подпрограмме будет такой:

занесение Z в стек занесение Y в стек занесение X в стек занесение адреса возврата в стек вход в подпрограмму

При входе в подпрограмму состояние стека будет таким:

s

Мы ставим в соответствие стеку еще один указатель L, который показывает на связь (адрес возврата) текущей подпрограммы; таким образом, имеем

*|С^зь|

L S

Итак, подпрограмма может обращаться к своим аргументам, ссылаясь на L, так как i-й аргумент должен находиться в стеке в регистре L — I. В качестве рабочего поля подпрограмма использует часть стека, находящуюся за связью. Для того чтобы эта система стала работоспособной, требуется следующее добавление: связь должна содержать не только адрес возврата, но также и указатель на связь для самой последней из ранее активизированных подпрограмм, т. е.

ф А

L S

Теперь работа по выходу из подпрограммы состоит в передаче управления по адресу возврата и в перемещении указателя L. В результате восстанавливается то состояние стека, которое имело место при входе в подпрограмму. Если подпрограмма выработала какие-то результаты, то операция выхода должна включать в себя копирование результатов на место аргументов. Например, предположим, что внутри подпрограммы S1 имеется обращение к подпрограмме S2, которая использует аргументы х и у и вырабатывает результат г. Тогда на различных этапах будут возникать следующие состояния стека:

При входе в S1

L S

При входе в S2

']#|^|(?to|

1 S

Во время работы S2 (непосредственно перед выходом)

— 1*Ш*Н .

4

После выхода из S2

Теперь результат г занимает ту ячейку стека, которую первоначально занимал аргумент у. Заметим, что с точки зрения подпрограммы S1 как бы выполняется операция «Занести х в стек», поскольку не остается других следов от работы подпрограммы S2.

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

При использовании этого метода можно обеспечить изящное единообразие, если выполнять в стеке также и арифметические операции, выбирая из стека два операнда и оставляя в «стеке один результат, например:

сложитьсложить

сложить

сложить

Нужна также тестовая операция, которая сравнивает два верхних элемента стека и записывает в стек результат true (Г) или false (Т7) в зависимости от того, одинаковы или различны эти элементы. Кроме того, требуется операция ППИ условного перехода при истине, которая осуществляет передачу управления, если верхний элемент стека имеет значение true и исключает из стека верхний элемент независимо от того, происходит или нет передача управления.

При наличии этих операций программа вычисления factorial (п) в соответствии с определением

factorial (п) = [и = 1 -> 1, п X factorial ^п — 1)]

демеет следующий вид:

Занести первый аргумент в стек

Занести константу 1 в стек

Применить тестовую операцию

Перейти на 10, если вершина стека = true

Занести первый аргумент

Занести константу 1

Вычесть

Обратиться к программе вычисления факториала

Занести первый аргумент

Умножить

Выйти из программы, оставив в стеке один результат 10 Занести константу 1

состояния стека на различных этапахсостояния стека на различных этапахВыйти из программы, оставив в стеке один результат

состояния стека на различных этапах

состояния стека на различных этапах

На рис. 3.1 показаны вычисления factorial (3)

|3|*|S|3|*|S* означает связь* означает связь

|3|*|

S

|3|*|

S

* означает связь

* означает связь

—™|3|*|ЗЦ|—|3|*|F|—131 *|3|1| |3| * |2|—13|*|2|*|—™|3|*|ЗЦ|—|3|*|F|—131 *|3|1| |3| * |2|—13|*|2|*|—13| #|2|* |2|11 —|3l*|2|#|F| ™|31*|2|#|2|1| —|3|*12|*|1| ' -131*12!*Ц| #1—13| #|2|* |2|11 —|3l*|2|#|F| ™|31*|2|#|2|1| —|3|*12|*|1| ' -131*12!*Ц| #1—-|3|#|2|*|1|*|1|1||3|#|2|*|1|*|Л—131#|2|*|1|#|1|131*121*111—-|3|#|2|*|1|*|1|1||3|#|2|*|1|*|Л—131#|2|*|1|#|1|131*121*111™-|3|*|2|#|1|2|~|3|#|2|#|2|-|3|*|2|™-|3|*|2|#|1|2|~|3|#|2|#|2|-|3|*|2|

—™|3|*|ЗЦ|

—|3|*|F|

—131 *|3|1| |3| * |2|

—13|*|2|*|

—™|3|*|ЗЦ|

—|3|*|F|

—131 *|3|1| |3| * |2|

—13|*|2|*|

—13| #|2|* |2|11 —|3l*|2|#|F| ™|31*|2|#|2|1| —|3|*12|*|1| ' -131*12!*Ц| #1

—13| #|2|* |2|11 —|3l*|2|#|F| ™|31*|2|#|2|1| —|3|*12|*|1| ' -131*12!*Ц| #1

—-|3|#|2|*|1|*|1|1|

|3|#|2|*|1|*|Л

—131#|2|*|1|#|1|

131*121*111

—-|3|#|2|*|1|*|1|1|

|3|#|2|*|1|*|Л

—131#|2|*|1|#|1|

131*121*111

™-|3|*|2|#|1|2|

~|3|#|2|#|2|

-|3|*|2|

™-|3|*|2|#|1|2|

~|3|#|2|#|2|

-|3|*|2|

проверка равенства обнаружено неравенство вычитание

рекурсивное обращение для вы

числения factorial (2)

проверка равенства обнаружено неравенство вычитание

рекурсивное обращение для вычисления factorial (1)

проверка равенства обнаружено равенство

factorial (1) = 1

выход, копирование результата в стеке; возобновление вычисления factorial (2)

умножение

factorial (2) =2

выход, копирование результата в стеке; возобновление вычисления factorial (3)

—™|3|*|2|3|—™|3|.*|6{—16| f 5—™|3|*|2|3|—™|3|.*|6{—16| f 5умножение

—™|3|*|2|3|

—™|3|.*|6{

—16| f 5

—™|3|*|2|3|

—™|3|.*|6{

—16| f 5

factorial (3) = 6

выход, копирование результата в стеке.

Рис.Рис.3.1. Вычисление factorial (3) с использованием стека.

Рис.

Рис.

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

(Л + В) X С

в обратной польской записи приобретает вид

свл + х

и ему соответствуют следующие операции над стеком:

занести СС

занести В СВ занести Д СВ А сложитьСа(а = А + В)

умножить р(р — С X «)

Аналогично, если мы расширяем возможности работы со стеком и включаем в них применение функций, то вычислению

f(al, а2, ..

., ап) соответствует следующая последовательность

операций:

занестиап

занестиап_х

занестиах

применитьf

Здесь операция «применить f» означает запись в стек связи (адреса возврата) и обращение к программе вычисления f. Таким образом, компилирование для такой системы сводится' в сущности, к преобразованию выражений в обратную польскую запись.

Способы повышения эффективности

Такая система, как описанная в предыдущем разделе, обеспечивает очень удобный способ обработки рекурсивных процедур, но для нерекурсивных процедур ее применение оказывается неэффективным, поскольку в этом случае нет необходимости организовывать управление стеком. Если программа составлена в основном из рекурсивных процедур (что типично для программ на языке ЛИСП), то неэффективность применения этой системы к нерекурсивным процедурам не имеет значения. Однако если рекурсивные процедуры образуют только малую часть программы (что типично для программ на АЛГОЛе), то неэффективность применения стека для нерекурсивных процедур может оказаться дорогой платой за удобство рекурсии. Поэтому некоторые системы (например, PL/1, CPL) требуют от программиста явных указаний относительно того, какие процедуры должны обрабатываться как рекурсивные. Были предложены методы автоматического выявления рекурсивное™, и мы коснемся двух из них.

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

Второй способ применяется в компиляторе с языка АЛГОЛ для машины KDF9; он описан Хокинсом и Хакстейблом [8]. Этот способ основан на том, что во время компиляции выясняется, возможны ли для той или иной процедуры рекурсивные обращения; после этого рекурсивные и нерекурсивные процедуры компилируются^ по-разному 9. Так как во время компиляции удается только отличить процедуры, которые заведомо не могут вызываться рекурсивно, от тех процедур, к которым как будто бы возможны рекурсивные обращения, то такая система будет в некоторых случаях генерировать рекурсивное обращение к процедуре, которое никогда не понадобится. Например, если тело процедуры Р1 не содержит никаких обращений к процедурам, то очевидно, что эта процедура никогда не будет вызы-

Метод предварительного формального выделения рекурсивно используемых процедур получил дальнейшее развитие в статье В. И. Собельмана «Выделение рекурсивно используемых процедур в АЛГОЛ-60», опубликованной в сб. «Цифровая вычислительная техника и программирование», вып. 2 (изд-во «Советское радио», М„ 1967). — Прим, перев.

ваться рекурсивно. С другой стороны, рассмотрим процедуру Р2, которая содержит оператор вида

if b then Р2 else РЗ

Очевидно, что к процедуре Р2 возможно рекурсивное обращение, хотя может оказаться, что во время счета переменная b всегда принимает значение false и поэтому рекурсивное обращение никогда не произойдет.

Если процедура описана рекурсивно, то легко обнаружить это во время компиляции. Более интересен случай «косвенной» рекурсии, примером которого является следующая последовательность обращений:

Р1 вызывает Р2 вызывает РЗ вызывает Р1

Для того чтобы обнаружить такой вид рекурсии, необходимо проследить структуру обращений в программе. Метод, примененный Хокинсом и Хакстейблом, состоит в том, что сначала организуется булевская матрица, в которой строки и столбцы соответствуют процедурам таким образом, что элемент (t,/) принимает значение 1, если процедура i может обратиться к процедуре j. Единицы в исходном состоянии матрицы соответствуют непосредственным обращениям. Например, предположим, что имеются пять процедур Pl, Р2, ..., Р5 и

Р1 содержит обращения к Р2, РЗ, Р4

Р2 содержит обращения к РЗ

РЗ не содержит обращений к процедурам

Pi содержит обращения к Pl, Р5 Р5 содержит обращения к РЗ, Pi

Исходная матрица имеет вид

0 1110

00001

00000

10001

00110

Далее заметим, что если процедура Pt содержит обращение к Pj, то Pt имеет «доступ» ко всем обращениям, содержащимся в процедуре Р/, поэтому полная структура обращений может быть получена применением к исходной матрице следующего алгоритма.

Пусть матрица — это boolean array В\\\п, 1 : п\

begin integer ц j, k, р;

for р: = 1, 2 do

for j: = 1 step 1 until n do

for z: = 1 step 1 until n do begin if В [z, /] then begin for k: = 1 step 1 until n do

bu, k]: = B[i9 k]y B[j, k] end;-

end;k

end;

Воршелл [9] показал, что для построения матрицы всех связей1) достаточно двух проходов по матрице, как в приведенной выше программе на АЛГОЛе. Если применить этот алгоритм к рассмотренному выше примеру, то получится матрица:

1 1 1 1 П 11111 0 0 0 0 0 11111 11111

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

При анализе программ на языке АЛГОЛ возникают дополнительные сложности, связанные с тем, что какая-то процедура может оказаться формальным параметром другой процедуры. Поэтому необходимо исследовать структуру соответствий между формальными и фактическими параметрами. Если читатель интересуется этой проблемой, то он может подробно ознакомиться с ней в статье Хокинса и Хакстейбла.

Стековая система для АЛГОЛа

Большинство компиляторов с языка АЛГОЛ вырабатывают такие программы, которые используют стек в процессе счета (см., например, у Ренделла и Рассела [10]). Применяемая при этом стековая система в основном аналогична системе, описанной в разд. 3.6; однако в ней имеется одна дополнительная особенность, связанная с областями действия описаний. В языке АЛГОЛ область действия идентификатора, т. е. та часть программы, в которой этот идентификатор имеет смысл, определяется лексикографически как блок, в котором этот идентификатор описан вместе с любыми внутренними блоками, если в них не описан такой же идентификатор. Поэтому могла бы встретиться такая структура:

9 То есть прямых и косвенных обращений. — Прим, перев.(

Области действия идентификаторов аbс

begin real а;

begin real b;

end;

begin real c;

end;

end;”

Такую блочную структуру очень удобно реализовывать в рамках стековой системы: блок рассматривается к$к процедура без параметров, и при входе в блок регистры стека, непосредственно следующие за связью, отводятся для переменных, описанных в начале блока. Таким образом, аналогично тому как для процедуры 1-й аргумент находится в ячейке L — i, точно так же t-я по счету описанная в блоке переменная находится в ячейке L + L При этом легко решается проблема путаницы имен, возникающая при повторном описании переменной с таким же именем, как у описанной ранее переменной. Область памяти, соответствующая локальным переменным какого-то блока, возвращается системе при выходе из этого блока. Кроме того, если блок является частью рекурсивной процедуры, то при каждой активизации (т. е. при каждом рекурсивном обращении) образуется новый набор локальных переменных, а при каждом соответствующем выходе восстанавливается предыдущий набор локальных переменных.

Положение усложняется, если включить в рассмотрение описания процедур. Рассмотрим следующий фрагмент программы:

begin real а;

procedure Q;

begin real b;

end;

begin real c;

Q;

end;

Q;

end;

Поскольку области действия переменных определяются лексикографически, то в пределах процедуры Q определены только переменные а и Ь. Непосредственно перед первым обращением к Q действуют описания для а и с\ непосредственно перед вторым обращением к Q действует только описание для а. Теперь нужно руководствоваться таким правилом: если переменная не - описана в начале того блока, в котором она используется, то нужно проверить описания в начале непосредственно объемлющего ее блока и т. д. Поэтому необходимо сохранять в стеке «статическую цепь», соединяющую «связи» для тех блоков, описания из которых в текущий момент доступны в указанном выше смысле. Эта цепь является добавлением к «динамической цепи», которая уже существует в стеке и соединяет связи тех процедур (блоков), в которые был осуществлен вход, а соответствующего выхода еще нс было. (Указатели из связей в стеке из разд. 3.6 образуют динамическую цепь.) Для повышения эффективности статическая цепь обычно дублируется вне стека; если читатель интересуется дальнейшими подробностями, то ему следует обратиться к статье Дийкстра [11] или книге Ренделла и Бассела [10].

Система рекурсии для языка ЛИСП

Язык ЛИСП допускает (и в сущности подразумевает) ре- курсивность всех функций. Система программирования на языке ЛИСП может быть реализована с использованием стековой системы, аналогичной той, которая описана в разд. 3.6. Первоначальная система ЛИСП 1.5, реализованная впервые на машинах IBM 7090/94, использует стек, элементами которого являются блоки регистров, причем каждый блок содержит информацию о своей длине и о соответствующем месте в памяти, откуда он появился, а также содержит имя той процедуры, которой он принадлежит. Эти имена процедур позволяют организовать полезную систему диагностики ошибок, так как путем исследования стека можно проследить последовательность тех функций, в которые был осуществлен вход. Эта «обратная последовательность» обычно печатается после любой ошибки.

ЗЛО. Аппаратные стеки

Стековые системы, описанные в предыдущих разделах, реализуются с помощью программного обеспечения. Однако можно иметь аппаратные стеки. Такие стеки предусмотрены, в частно- <сти, в английской машине KDF9 [12] и в машине Burroughs В5000 [13, 14].

Стек машины KDF9. В машине KDF9 имеются два аппаратных стека: «хранилище переходов для вложенных подпрограмм» и «магазинный сумматор». Каждый из них состоит из 16 ячеек. Как следует из его названия, хранилище переходов для вложенных подпрограмм используется для хранения адресов возврата из подпрограмм.. При входе в подпрограмму адрес возврата заносится на вершину стека; операция выхода включает в себя передачу управления по адресу, находящемуся на вершине стека, и продвижение содержимого стека вверх. Магазинный сумматор является стеком, в котором предусмотрена возможность выполнения арифметических операций над верхними двумя элементами; поэтому машинные арифметические команды приобретают вид строки в обратной польской записи. Кроме того, предусмотрены некоторые операции перемещения, которые выполняются над верхними двумя, тремя или четырьмя ячейками стека: например, обмен местами двух верхних элементов, дублирование верхнего элемента, циклическая перестановка верхних четырех элементов и т. д. Магазинный сумматор удобен для вычисления арифметических выражений именно тем, что он допускает строку команд в обратной польской записи. (Это экономично, так как адреса требуются только для команд выборки операндов.) Однако стековая система такого вида только в очень ограниченных случаях облегчает рекурсивное программирование. Например, поскольку хранилище переходов для вложенных подпрограмм содержит только шестнадцать регистров, то, даже если бы удалось преодолеть остальные трудности, максимальное значение возможной глубины рекурсии нс превышало бы шестнадцати.

Burroughs В5000. Машина В5000 представляет особый интерес. Ес аппаратура обеспечивает стековую систему, которая к основном соответствует системе, описанной в разд. 3.6. Стек хранится в ферритовой памяти pi может иметь неограниченную длину; поэтому он действительно обеспечивает все возможности для рекурсивных процедур. (Аппаратный стек является только одной из многих интересных особенностей этой машины. Например, операндные ссылки на стек называются дескрипторами, и в зависимости от содержимого определенных управляющих разрядов из машинного слова остальная часть содержимого поля операндов может интерпретироваться либо как операнд, либо как указатель операнда, либо как адрес подпрограммы, которая вычислит указатель операнда.)

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

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

Здесь Fa и Fb— флажки занятости для аппаратных регистров А и В. Условно мы будем обозначать свободное состояние че- д)ез 0, а занятое через 1. На схеме 3.2 показана последователь-

Строка в польской записи: ab + cd + X

(ос = и 4- Ъ}

(Hc^d^

(1 = «хр)

Рис. 3.2. Действие стека машины Burroughs В5000.

ность событий при вычислении выражения (а + b) X (с + d) в предположении, что в начальный момент стек пуст.

При выполнении обращения к подпрограмме нужно запомнить в стеке текущее содержимое аппаратных регистров. Поэтому если Fa = I или FB = I, то перед началом выполнения стандартного входа в подпрограмму содержимое соответствующего регистра переносится в стек. Таким образом, вход в подпрограмму производится при пустых аппаратных регистрах.

6565Список литературы

65

65

СПИСОК ЛИТЕРАТУРЫ

Dijkstra Е. W., Recursive programming, Numerische Math., 2, № 5, p. 312.

Baecker H. D., Gibbens B. J., A commercial use of stacks, Ann. Rev. Automatic Programming, 4, p. 183. Ed. R. Goodman, Pergamon, 1964.

Strachey C., A general purpose macro generator, Computer. J., 8, № 3 (1965), 225.

Ayer A. J., Commun. Assoc. Computing Machinery, 6, № 11 (1963), 667.

FAP Reference Manual, IBM Publication No. C28—6235.

Newell A. (ed.), Information processing language-V manual, Prentice-Hall, 1961.

Irons E. T., Feuerzig W., Commun. Assoc. Computing Machinery, 4, № 1 (1961) , 65.

Hawkins E. N., Huxtable D. H. R., A multi-pass translation scheme for ALGOL 60, Ann. Rev. Automatic Programming, 3, p. 316.. Ed. R. Goodman, Pergamon, 1963.

Warshall S., A theorem on Boolean matrices, J. Assoc. Computing Machinery, 9 (1962), 279.

Randall B., Russell L. J., ALGOL 60 jmplementation, Academic Press, 1964. (Русский перевод: Рендел Б., Рассел Л., Реализация АЛГОЛа-60, «Мир», М., 1967.)

Dijkstra Е. W., Making an ALGOL translator for the XI, Reprinted in Annu. Rev. Automatic Programming, 4. Ed. R. Goodman, Pergamon, 1963.

Davis G. M., The English Electric KDF9 computer system, Computer Bull.* 4, № 3 (1960), 119.

Burroughs Corporation, Operational characteristics of the processors for the Burroughs B5000.

Barton R. S., A new approach to the functional design of a digital computer, Proc. Western Joint Computer Conf., 1961, p. 393.

Введение

В этой главе мы изучаем формальное соотношение между рекурсией и итерацией. Утверждение, что «все рекурсивные связи могут быть сведены к рекуррентным или итеративным описаниям», уже обсуждалось в гл. I. Данная глава начинается с наброска возможного способа формального доказательства истинности этого утверждения для широкого класса числовых функций. Установив, что определенные функции могут быть описаны с помощью рекурсивной или итеративной схемы, мы затем рассматриваем такой подход, с точки зрения которого эти описания могут считаться эквивалентными, и исследуем возможность автоматического преобразования из одной формы в другую. Используемые идеи в основном заимствованы у Маккарти [1, 2] и развиты Купером [3]. У Маккарти интерес к этой отрасли возник в связи с его попытками создать основы теории вычислений. Возможность доказательства эквивалентности программ интересует его как средство формального доказательства правильности программы вместо того, чтобы демонстрировать ее правильную работу для отдельных наборов тестовых данных.

Вычислимые функции

Этот раздел содержит краткий обзор теории вычислимых функций. С полным изложением этой теории читатель может познакомиться1) по книге Дэвиса [4]. Отправной точкой является определение примитивно рекурсивной функции. (Заметим, что слово «рекурсивная» несет в данном контексте несколько специализированную смысловую нагрузку: оно относится не к самим функциям, а к тому методу, с помощью которого определяется класс функций.) Можно определить примитивно ре-

*) На русском языке теория вычислимых функций систематически изложена в монографии В. А. Успенского «Лекции о вычислимых функциях» (Физматгиз, М., 1960). — Прим, перев.

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

(1)

S(x) = x+ 1

(2)

jV(x) = 0

(3)

U"(хь ..., хп) = Xi (1 ^ i ^ га)

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

Функция х + у является примитивно рекурсивной, так как

х + 0 = С7;(х)я + (у+ i)=s(x + y)

Функция хХу является примитивно рекурсивной, так как

xX0 = M(x)

^X(t/ + 1) = U +у)+ <71 (X, у)

Функция ху является примитивно рекурсивной, так как x? = S(N(x^

xy+x=xvXUUx, У^

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

Функция и! является примитивно рекурсивной, так как 0! = S^(x))

(«+!)! = «! XS^n)

Функция предшествования /’(х), где Р(0) =0 и Р^х) — ■ = х— 1, если х > 0, является примитивно рекурсивной, так как:

P(0) = ^(x)P(x+l)=t/}(x)

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

Интуитивно ясно, что функции, описанные таким способом, могут быть вычислены либо с помощью рекурсивной, либо с помощью итеративной программы. Райс [5] приводит программу на языке ФОРТРАН IV, которая может в принципе вычислить любую примитивно рекурсивную функцию, используя итеративный цикл.

Функции и блок-схемы

Характерным признаком итеративного процесса является то, что его можно представить с помощью блок-схемы. Поэтому мы рассмотрим сначала проблему перевода итеративного процесса, представленного с помощью блок-схемы, в форму рекурсивной функции. Каждый этап итеративного процесса может рассматриваться как функция, оперирующая над входными данными этого этапа и вырабатывающая выходные данные. Поэтому, ^сли процесс состоит из последовательности подпроцессов А, В* С, то мы можем представить его выполнение в виде

с(&(аО '

где £— вектор, представляющий состояние машины, а — функция, эквивалентная процессу А и т. д. Поэтому имеем

t «О

А

в

~Т~ <WD))

с

Теперь предположим, что процесс содержит условный переход:•

Пусть блок А представляется функцией а^, блок С — функцией с (В), а вся программа — функцией f^). Мы можем представить всю программу в виде

где

s а)=\ь-ч а), с®]

или, более кратко, Н£) = №.[6->т с О [а а)].

Теперь рассмотрим проблему перехода от рекурсивного описания функции к блок-схеме. Возьмем в качестве примера описание факториальной функции:

Factorial (п) = ф ^п, 1) где

Ф^п» s) = [(м = 0) -> s, ф (п — I, п X s)]

Вектор состояния для этого вычисления состоит из значений п И S, Т; с.

Предположим, что мы описали две функции:

^(n, s) = (га, »Xs}f2(n, s)= {n — 1, s}

Тогда можно записать ^(n—1,«Х$) в виде ^(f^(fi(га, s))) и описание функции ^ принимает следующий вид:

№ s) = [(n = 0)-*s, Ж(М«> s)))]

Если предикат п = 0 представляется функцией f3(n, s), то мы получаем запись

которая сразу переводится в блок-схему:

Читатель может убедиться, что эта блок-схема эквивалентна программе:

a; if п = 0 then go to b;

s : = nXs;

n: = n — 1;

go to a;

b:

Если теперь мы попытаемся применить тот же процесс к другому описанию факториальной функции:

ZW = [(^ = O)->1, nXf(n — 1)]

то встретимся с трудностями. Полученная при этом блок-схема имеет следующий вид:

Здесь заштрихованный прямоугольник представляет весь процесс вычисления факториальной функции. Это эквивалентно процедуре на языке АЛГОЛ, которая рекурсивно обращается к себе. Таким образом, существуют некоторые рекурсивные описания, которые нс могут быть прямо переведены этим способом в итеративные процедуры. (Из этого нс следует, что существуют математические функции, которые могут быть вычислены только вычислительными системами, допускающими рекурсию. Мы должны четко уяснить разницу между математическим описанием функции и программой, вычисляющей эту функцию.)

Маккарти формально определил различие между теми рекурсивными описаниями, которые переводятся прямо в итеративные процедуры, и теми, которые не переводятся.

В общем случае если

f(x„ .... х„) = е(/, Х„ . Хп, gi, .... gm)

где в — какое-то выражение (обычно условное), и g^ ..., gm— функции, то / называется функцией итеративного типа, если f никогда не встречается в качестве аргумента какой-либо из функций gt. Если это условие выполняется, то можно начертить блок, представляющий /, и каждое появление f в правой части

описания переводится в возврат к началу процесса. Но если f встречается в качестве аргумента одной из функций gt, то появление f в правой части описания будет переводиться в блок, представляющий весь процесс.

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

Эквивалентность описаний

Мы показали, что если задано рекурсивное описание в «итеративной» форме, то его можно перевести в итеративную программу. Следующим этапом является поиск способа доказательства эквивалентности двух описаний одной и той же функции. Такое формальное доказательство явилось бы существенным шагом на пути к автоматическому переводу неитеративного описания функции в итеративное описание. Рассмотрим два описания факториальной функции в несколько различных формах:

Factorial (п) = [(п = 0) —> 1, R ^п, Factorial (d (n)))](1)

Factorial (п) = ф(п, 1)(2)

Ф^п, щ) = [(/г = 0) ~> m, ^(6 (и), Р^п, т))]

В этих описаниях использованы вспомогательные функции д(м) = м— 1

Р^п, т^ — пХпг

Из описания (1) следует, что

Factorial^) = Р(п, Р^^п^ Р(д2(п\ ..., Р^-Цп^ 1) ...))(3)

а из описания (2) получаем

Factorial^ = P(dx”I(/i), ..., P(d2(n), P(dH P(n, 1)) ..,.))) (4)

где 62(n) = S(6(n)) и т. д., X— целое число, такое, что 6х (я) = = 0.

Функция Р обладает тем свойством, что Р(а, Р(р, у)) = = Р(р, Р(а,у)). Последовательно применяя это соотношение, мы можем переместить самое глубокое вхождение Р в формуле (4) в начало выражения. Затем тот же процесс может быть повторен для нового самого глубокого вхождения Р и так далее до тех пор, пока мы не получим, наконец, равенство (3). Таким образом, будет доказана эквивалентность двух рассматриваемых описаний факториальной функции.

В частном случае имеем.

Factorial (3) = ^>(3, 1)

t(3, 1) = ^>(2, Р(3, 1))

= t(l, Р^, Р^, 1)))

= ^(0, Р(1, Р^, Р^, 1))))

= Р(1, Р^, Р^, 1)))

Последнее выражение имеет вид (4).

Однако'

Р(1, Р^, РУ,, 1))) = Р(1, Р(3, Р(2, 1)))

= Р(3, Р(1, Р(2, 1)))

= Р(3, Р(2, Р(1, 1)))

т. е. мы получили вид (3).

Можно обобщить этот принцип.

Предположим, что заданы описаниях

Я (п) = [(и = L) -> В, Н (п, Я (6 (га)))](5)

£2 (га, Д) = [(га = L) -> A, G (6 (га), Е (п, Д))](6)

Они идентичны нашим предыдущим описаниям (1) и (2) с той разницей, что числа 0 и 1 заменены соответственно на L и В и произведение Р заменено на функцию Я в (5) и на функцию Е в (6). Купер [3] показал, что эквивалентность этих двух функций может быть доказана, если при некотором значении константы В

Н (а, В) = Е(а, В)(7)

и

Я (о, £ (Р, у)) = £ (р, Я (а, у))(8)

Доказательство проводится таким же способом, как и в предыдущем случае. Из исходных описаний получаем

Factorial <п) = Н(п, Н (Цп), И (б2 (га), .... Н ^~Чп\ В), ...)) (9)

Factorial^') = Е^Х-Цп)£(б2(га), £(д(га), £(га, В)), ...)) (10)

Применив соотношение (7), можно заменить в формуле (10) самое глубокое вхождение Е на Н. Затем, последовательно применяя соотношение (8), можно переместить это вхождение Н в начало выражения. Такой процесс повторяется до тех пор, пока не исчезнут все вхождения £; полученный при этом результат будет идентичен формуле (9).

Предположим теперь, что N — список, б[Я]— операция исключения первого элемента списка, HVN, Д] — список, получае-

мый добавлением первого элемента списка N в конец списка Д, В и L — пустые списки. На языке ЛИСП это записывается так:

d[M] = Cdr[W]

H[N; Д] = Append [Car [N]; Д]

B — L —ПУСТО

Тогда

■ Fi (W) = [Null [N] -> ПУСТО’,

•Append[Car[N]; F\ [Cdr[M]]]]

Это рекурсивная функция переворачивания списка )• Аналогично

F^(N^ = G\N; ПУСТО] где

G[N; A] = [Null[N]-+A;

G[Cc?r [TV]; Е[п; Д]]]

Если мы сумеем найти функцию Е, удовлетворяющую условиям (7) и (8), то получим эквивалентное описание в итеративной форме.

Итак,

H[N; А] = Append [Car [N]; Д]

Поэтому

И [a; E[b; с]] = Append[Car[a]; E[b; с]]

В результате применения последней формулы получаем список (Е[&; с], Саг [а]).

Если E[b; с] = Cons [Саг [6]; с], то выражение Н[а; Е[Ь; с]] даст нам список [Саг [6], с, Car [а]). С другой стороны,

E[b; Н[а; с]] = Cons [Саг [6]; Н [а; с]]

= Cons [Саг [6]; Append [Саг [а]; с]]

что также дает список (Саг [й], с, Саг [а]).

Итак, E[N, ПУСТО] = H[N, ПУСТО], так что условия (7) и (8) удовлетворяются.

Таким образом, мы располагаем методом преобразования любого описания типа (1) в эквивалентное итеративное описание, если умеем найти подходящую функцию Е.

Можно описывать такие методы в виде некоторых подробных доказательств теорем относительно какого-то ограниченного класса программ. Непосредственной задачей дальнейших исследований в этой области должно быть получение менее глубоких

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

СПИСОК ЛИТЕРАТУРЫ

McCarthy J., Towards a mathematical science of computation, in Information processing 1962, Proceedings of the IFIP Congress, 1962, ed. С. M. Popplewell, North Holland, 1963.

McCarthy J., A basis for a mathematical theory of computation, in Computer programming and formal systems, ed. B. Braffort and D. Hirschberg, North Holland, 1963.'

Cooper D. C., The equivalence of certain computations, Computer J., 9, № ( (1966), 45.

Davis M., Computability and unsolvability, McGraw-Hill, 1958.

Rice H. G,. Commun. Assoc. Computing Machinery, 8, № 2 (1965), 114.

ПРИЛОЖЕНИЕ

Обработка списков

Это приложение содержит очень краткий обзор методов обработки списков и предназначено для читателей, которые незнакомы с этим предметом. С дальнейшими подробностями читатель может ознакомиться по статье Маккарти [1] и по книге Фостера [2].

Списковая структура представляет собой некоторое размещение атомов. Атомы могут являться любыми комбинациями символов. Для наших целей необходимо выполнение одного существенного условия, что атомы — это неделимые объекты. Например, «ВСЕЧТОВАМУГОДНО»— единый атом. В дальнейшем мы будем обозначать атомы прописными буквами.

Простой список представляет собой линейную последовательность атомов, например:

(А, В, С, D)

(А)

Отметим разницу между атомом А и списком (А), состоящим из одного элемента, причем этот элемент является атомом А.

Можно определить списковую структуру как список, элементами которого являются либо атомы, либо списки. Таким образом, структура

(А, (В, С), D) представляет собой список из трех элементов, причем вторым элементом является список (В, С). Структура

((А, (В, С)), (D, Е))

представляет собой список из двух элементов; первый элемент, в свою очередь, является списком, составленным из атома А и списка (В, С). Можно получить список вида

■(((А)))‘

Это список из одного элемента, являющегося списком из одного элемента, который представляет собой список из одного элемента, атома А. Занимаясь списковыми структурами, мы имеем

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

Основными функциями для обработки списковых структур являются следующие: "

(a) Саг [г] или Hd(z} Значением этой функции(a) Саг [г] или Hd(z} Значением этой функциисписка 2.Таким образом:списка 2.Таким образом:является первый элементявляется первый элемент2(А, В, С)(А, (В, С))((А, В), С)((A))(А)2(А, В, С)(А, (В, С))((А, В), С)((A))(А)Hd^АА(А. В)(А)АHd^АА(А. В)(А)А

(a) Саг [г] или Hd(z} Значением этой функции

(a) Саг [г] или Hd(z} Значением этой функции

списка 2.

Таким образом:

списка 2.

Таким образом:

является первый элемент

является первый элемент

2

(А, В, С)(А, (В, С))((А, В), С)((A))(А)

2

(А, В, С)(А, (В, С))((А, В), С)((A))(А)

Hd^АА(А. В)(А)А

Hd^АА(А. В)(А)А

Cdr[z] или Il [z]

' Значением этой функции является та часть списка z, которая остается после удаления из списка первого элемента *). Если за первым элементом ничего не оказалось, то значением П[г] является пустой список ПУСТО). (ПУСТО, Т (истина) и F (ложь) являются универсальными константами системы.) Таким образом:

zTl (z)

(А, В, С)(В, С)

(А, (В, С))((В,С))

((А, В), С)(С)

((A))ПУСТО

(А)ПУСТО

Cons\x; у]. Значение этой функции — новый список, в котором началом является х, а остальной частью — у. Таким образом:

хуCons[x\ t/]

А (В, С) (А, В, С)

(А, В)(С)((А, В), С)

(А)(В)((А), В)

АПУСТО(А)

(А)ПУСТО((A))

Заметим, что Cons [Hd [х]; П[х]] = х.

’) Аналогично Caar [z] — первый элемент первого элемента списка г, Cadr [z] — первый элемент остатка списка г и т. д. — Прим, перев.

(г) Atom, [х] принимает значение „истина" тогда и только тогда, когда х является атомом.

Null\x\ принимает значение „истина" тогда и только тогда, когда х является атомом ПУСТО.

Eq\x; у] принимает значение „истина" тогда и только тогда, когда х и у — атомы, причем х = у. Значение этой функции не определено, если х или у не является атомом.

Остальные функции описываются через Hd, Т1 и Cons с помощью условных выражений, в которых используются предикаты Atom, Null и Eq. Например:

EqualVx; у] принимает значение „истина" тогда и только тогда, когда х и у — одинаковые атомы или х и у — идентичные списковые структуры.

EqualVx; y] = [Atom[x]—> AiomVy] A Eq\x, у],

AiomVy]-*Ff

Equal [Hd[xh Hd [yll Д Equal [Т1 [х]; ТЦуЩ

/?еи[х]. Значением этой функции является список, который содержит такие же элементы, как и список х, но эти элементы располагаются в обратном порядке. Например:

Rev [(А, В, (С, D))] = ((С, D), В, А)

Для получения функции Rev используем формулу:

Rev [х] = Reva [х; ПУСТО] где

Reva [а; 6] = \Null [а] -► Ь,

/?еиа[П[а]; Cons[/fd[a]; b]]]

Списковая структура обычно представляется в вычислительной машине последовательностью ячеек, каждая из которых разделяется на две части. Одна часть содержит очередной элемент списка, а другая — указатель на следующую ячейку. Это означает, что для хранения списков не требуются идущие подряд ячейки. Список (А, В, С) был бы представлен следующим образом:

I—Га] I-*—Пв1к-ГсТ\1

Каждая стрелка означает, что соответствующая ячейка содержит указатель на следующий элемент. Символ

означает конец списка: его можно интерпретировать как атом ПУСТО. Если какой-то список содержит в качестве элемента другой список, то соответствующая ячейка первого списка содержит указатель на подсписок. Например, списковая структура (А, (В, С)) была бы представлена следующим образом:

Более сложными являются следующие списковые структуры:

((А, В), (С, D))

(((А)))

Итак, основные функции Hd и Т1 выделяют первую или вторую из двух частей ячейки. (Отсюда происходят другие названия тех же функций Car = Contents of Adress Register, т. e. содержимое регистра адреса, и Cdr = Contents of Decrement Register, т. e. содержимое регистра декремента. Эти названия отражают способ хранения списков при первоначальной реализации системы ЛИСП на машине IBM 7090.)

Список литературы!79

Для выполнения функции Cons (х, у) берется новая ячейка; х помещается в начальную часть этой ячейки, ссылка на у помещается в оставшуюся часть.

Следует заметить, что, хотя мы и говорим о двух частях ячейки, вовсе не обязательно, чтобы это были части одного л того же регистра. Например, если заданы две линейные последовательности НАЧАЛО и ОСТАТОК, то мы можем рассматривать в качестве f-й ячейки пару физических регистров НАЧАЛО (t) и ОСТАТОК ^iY Этот прием удобно использовать, если обработка списков включается в систему трансляции с языка АЛГОЛ.

СПИСОК ЛИТЕРАТУРЫ

McCarthy J., Recursive functions of symbolic expressions and their computation by machine, Commun. Assoc. Computing Machinery, 3, № 4 (1960), 104.

Foster J. M., List processing, Macdonald, 1967. (Русский перевод: Фостер Дж., Обработка списков, «Мир», М., 1974.)

ОГЛАВЛЕНИЕ

Пред;затора перевода и переводчика5

Пред ‘ 6

Основные понятиярекурсии7

Введение 7

Рекурсивные функции и процедуры7

Обработка рекурсивных данных12

Рекурсия в языках программирования13

Рекурсия в функциональном программировании14

Подсчет с помощью рекурсии17

Полезна ли рекурсия?17

Список литературы 19

Примеры и приложения21

Приложения к вычислениям21

Решение уравнений21

Рекуррентные соотношения22

Приближенное интегрирование23

Теория чисел25

Другие примеры из численного анализа29

Рекурсия в компиляторах29

Условные операторы29

Синтаксический анализ32

Сортировка 37

Обработка алгебраических выражений39

Системы решения проблем43

Список литературы 45

8. Средства реализации рекурсии46

Постановка задачи46

Специальные методы46

Стеки47

Основа для рекурсии50

Система IPL-V52

Обобщение понятия стека53

Способы повышения эффективности58

Стековая система для АЛГОЛа60

Система рекурсии для языка ЛИСП62

Аппаратные стеки62

Список литературы 65

4. Рекурсия и итерация66

Введение 66

Вычислимые функции66

Функции и блок-схемы68

Эквивалентность описаний .. 71

Список литературы74

Приложение. Обработка списков75

Список литературы 79

COMPUTER MONOGRAPHS General Editor: Stanley Gill Associate Editor: J. J. Florentin

RECURSIVE TECHNIQUES

IN PROGRAMMING

D. W. BARRON

MACDONALD; LONDON 1969

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ЭВМ

Д.Баррон РЕКУРСИВНЫЕ МЕТОДЫ

В ПРОГРАММИРОВАНИИ

Перевод с английского

В. В. Мартынюка Под редакцией Э. 3. Любимского

ИЗДАТЕЛЬСТВО

«МИР»

Москва 1974

УДК 681.142.2

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

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

Редакция литературы по математическим наукам

Д. Баррон