Лабораторная работа № 8 Программирование интеллектуальных систем на языке Пролог Рекурсия и рекурсивные процедуры в Прологе

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

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

Для того, чтобы погрузить N контейнеров, нужно:

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

Если N>0, то погрузить один контейнер, затем погрузить еще N-1 контейнер.

 Будем считать, что здесь дано определение процедуры "погрузка N контейнеров", где N - аргумент процедуры и обозначает некоторое целое число.

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

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

предок(А,Б):-родитель(А,Б). предок(А,Б):-родитель(В,Б), предок(А.В).

 Совокупность этих правил определяет два способа, в соответствии с которыми одно лицо (А) может быть предком другого липа (Б).

Согласно первому правилу, А является предком Б, если А - родитель Б, т.е. А является ближайшим предком Б.

Согласно второму. А будет предком Б, если есть некоторый В, который, являясь родителем Б, имеет своим предком А. Другими словами, А - предок Б, если А -предок родителя Б, т.е. А - отдаленным предок Б. Таким образом второе правило зависит от более простой версии самого себя, т.е. от подцели "предок".

Задание 1.

В программу 10 предыдуей лабораторной работы введите описание процедуры "предок". Выполните ряд произвольных запросов к программе. Используя режим трассировка, изучите последовательность обработки в Турбо-Прологе процедуры "предок". Сохраните программу в файле "lab8.pro"

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

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

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

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

Первое предложение процедуры "предок" определяет исходный вид процедуры. Как только данное предложение станет истинным, дальнейшая рекурсия прекратится. Говоря иначе, первое предложение является граничным условием.

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

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

Из определения факториала известно, что О! = 1, а факториал любого числа N может быть вычислен как факториал N-1, умноженный на N. Это определение является рекурсивным, поскольку сводит задачу нахождения N! к более простой задаче нахождения (N-1)! и затем умножения полученного значения на N.

/* программа 11 */

predicates

f(integer,integer)

clauses

f(U) :- !. f(N,R) :- M=N-1, f(M,V), R=V*N.

Для обозначения факта, что факториал числа N равен R, используем предикат f(N,R). Рекурсивное его определение будет иметь вид, приведенный в программе 11.

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

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

Задание 2.

Используя режим трассировки, изучите последовательность обработки рекурсивных процедур на примере вычисления факториала. Измените программу таким образом, чтобы она вычисляла сумму заданной последовательности целых чисел. Отладьте программу, а потом вычислите сумму первых тысячи чисел, сумму первых 10 тысяч чисел. Какой получился результат? Как его можно объяснить?