Декларативные языки программирования

Декларативные Языки Программирования

Определение понятия рекурсии

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

Для того чтобы съесть N штук алтея аптечного, нужно:

Если N = 0, то остановиться.

Если N > 0, то

проглотить одну штуку, затем

съесть N — 1 штук алтея аптечного.

Будем считать, что здесь приведено определение процедуры "съесть N штук алтея аптечного". Символ N — аргумент процедуры. Он обозначает некоторое целое число. Данная процедура рекурсивна, поскольку последняя строка — "съесть N - 1 штук алтея аптечного" — "является вызовом процедурой самой себя. Заметьте, что аргумент при рекурсивном вызове N — 1 проще, чем исходный аргумент N, в том смысле, что N— 1 — это меньшее число, чем N. Поэтому "съесть N штук алтея аптечного" представляет собой более сложный случай, выраженный через менее сложный случай выполнения тех же самых действий, т.е. через "съесть N — 1 штук алтея аптечного".

"Предок"

Классическим примером рекурсивного определения в Прологе может служить программа "предок", состоящая из двух правил:

предок (А, Б) :— %(1)

родитель (А, Б).

предок (А, Б) : —' %(2)

родитель (В, Б),

предок (А, В).

Совокупность этих правил определяет два способа, в соответствии с которыми одно лицо (А) может быть предком другого (Б). Согласно фразе (1), А является предком Б, если А — родитель Б. Согласно фразе (2), А будет предком Б, если А является предком родителя Б, т.е. предком В. Отношение, представленное в заголовке фразы (2), зависит от более простой версии самого себя — от подцели "предок".

Запросы к процедуре "предок "

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

родитель (жб, лц).

родитель (жб, гг).

родитель (гг, вм).

Нижеследующие запросы иллюстрируют использование правила "предок":

% является ли жб предком гг?

¦ ? - предок (жб, гг).

да % в соответствии с фразой (1)

% найти всех потомков жб:

¦ ?- предок (жб, П).

П=лц; % в соответствии с фразой (1)

П=гг; % в соответствии с фразой (1)

П=вм; по фразам (2) и (1

нет

Дерево доказательства, иллюстрирующее отношение "предок" для "жб" и "вм", представлено на рис. 1.2.

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

Состав рекурсивной процедуры

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

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

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

Неработоспособная версия процедуры "предок"

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

нпредок (А, Б) :— % (1)

родитель (А, Б).

нпредок (А, Б) :— % (2)

нпредок (А, В),

родитель (В, Б).

С декларативных позиций смысл этой процедуры идентичен смыслу процедуры "предок". Но при процедурной трактовке смысл процедур "предок" и "нпредок" существенно различается. В.процедуре "предок" подцель "родитель(В, Б)" рекурсивного правила вырабатывает новое значение переменной В, которое затем используется в рекурсивной подцели "предок (А, В)". С другой стороны, в процедуре "нпредок" переменная В не конкретизирована в момент обработки рекурсивной подцели "нпредок(А, В)". На практике это означает, что когда интерпретатор будет пытаться выполнить запрос к процедуре "нпредок", то вначале он, отыщет правильные ответы, а затем будет выполнять рекурсивные действия вплоть до исчерпания доступного объема памяти:

¦ ?- нпредок (жб, П).

П= ли;

П=гг

П=вм;

предупреждение: исчерпана стековая память.

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

Рекурсивная версия процедуры "можно_путешествовать"

Метод рекурсии, использованный при составлении процедуры "предок", можно с успехом применить и для написания процедуры "можно_путешествовать". В процедуре "можно_путешествовать4", текст которой приведен ниже, определяется отношение между двумя городами. Это отношение будет соблюдаться в том случае, если можно совершить путешествие из одного города в другой через любое количество промежуточных пунктов. Процедура "можно_путешествовать4" является рекурсивной. Она очень похожа на процедуру "предок". Предположим, что существует упомянутая ранее база данных "путешествие/4". Тогда отношение, определяемое процедурой "можно_путешествовать4", будет соблюдаться в те же случаях, что и для процедуры "можно_путешествовать2", а также и в ряде других ситуаций (скажем, для поездки между Бирлингтоном и Портлендом через Нью-Йорк и Бостон).

можно_путешествовать4(ГородА, ГородБ) :— %(1)

путешествие (_, ГородА, ГородБ, _).

можно—путешествовать4 (ГородА, ГородБ) :— % (2)

путешествие (_, ГородА, ГородВ, _),

можно_путешествовать4(ГородВ, ГородБ).

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

Порядок выполнения запроса к процедуре

"можно_путешествовать4"

Дерево доказательства, изображенное на рис. 1.4, иллюстрирует выполнение запроса к процедуре "можно_путешествовать4".

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

Вверх