|
Общие сведения о языке Пролог
В этом параграфе мы сначала на примере задачи «Ханойская башня» рассмотрим механизм «порождения» рекурсии, а затем на простых программах представим схему поиска решения.Следующий алгоритм печатает решение задачи о Ханойской башне на 7 дисках. Для понятливости будем писать термы русскими буквами:
Ханой (7, ‘A‘ ‘В‘,’С‘)
при
программа Ханой (аргументы n : ЦЕЛ, A, B, C : ЛИТЕРЫ)
(1) если n > 0 то
(2) Ханой (n - 1, A, C, B);
(3) печатать ("перенести кольцо с:’A’на ‘B’);
(4) Ханой (n — 1, C, B, A)
Что происходит, когда программа выполняет рекурсивный вызов, например первый такой вызов строки (2)? Выполнение подпрограммы прерывается с тем, чтобы тотчас возобновить ее выполнение сначала, но с новыми параметрами: n заменяется на n-1, A остается неизменным, B и C меняются местами. Можно сказать, что одно поколение Ханоя породило новое поколение той же подпрограммы с другими параметрами и впало затем в «зимнюю спячку».
Созданное таким образом поколение само может порождать новые поколения, и процесс будет повторяться, но не до бесконечности, а в зависимости от управляющей величины (в данном случае n), которая убывает при переходе к каждому новому поколению. Когда поколение, порожденное строкой (2), заканчивается или «умирает», породившее его материнское поколение возрождается для выполнения строки (3) при тех значениях параметров, какие оно имело в момент прерывания. Затем оно вновь порождает поколение (4) с n - 1, C, B и A в качестве новых параметров. По окончании этих дочерних поколений исходное поколение также заканчивается, так как (4) является последней строкой подпрограммы. И только в том случае, когда она выполняется старшим поколением, соответствующим n = 7, строка (4) порождает действительный возврат к программе, вызвавшей Ханой.
Как видно, задача управления рекурсией заключается в том, чтобы сохранить при каждом рекурсивном вызове информацию, необходимую для последующего поколения, инициировавшего этот вызов, и правильно отыскать эту информацию, когда предыдущему поколению вновь будет передано управление.
Какая же информация должна быть сохранена? Введем понятие «состояние программы», которое в каждый момент определяется значениями переменных и содержимым «указателя выполнения», т. е. указанием активного в этот момент оператора. Именно это «состояние» и следует сохранить перед каждым вызовом, имея в виду, что в число «переменных» здесь надо включать аргументы подпрограммы (в данном случае n, A, B, C), к которым добавляются локальные переменные, если они имеются, и возможный результат подпрограммы.
|
