Рекурсивные вычисления

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

Рекурсивное описание правила содержит в своем теле ссылку на заголовок этого же правила. При этом возможны следующие варианты рекурсивных правил:

1) правая рекурсия

pr1():-pr11(), pr12(), ..., pr1()

2) левая рекурсия

pr1():-pr1(),pr21(), pr22(),...

3) обобщенная рекурсия

pr1():-pr11(),pr12(),..., pr1(), pr21(), pr22() .....

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

1) заданием в программе альтернативного правила или факта рr1(), не содержащего рекурсии (выход произойдет при успешном выполнении этого альтернативного правила);

2) формированием условия выхода одним из предикатов рr11 (), рr12()... - выход происходит, если в процессе выполнения правила хотя бы один из предикатов завершается неуспехом.

Предикаты рr21(), рr22()...не влияют на выполнение рекурсии - Они выполняются только после выхода из нее и получают значения переменных из стека, в который они помещаются во время выполнения рекурсии. Производимые при этом вычисления называют хвостовыми вычислениями.

Основные идеи реализации рекурсивных определений в Прологе рассмотрим на примере вычисления факториала. Программа на Прологе имеет вид:

domains

number, product=integer

predicates

fact(number,product)

clauses

317

fact(N,R):-Next_N=N-1,

fact(Next_N,P),

R=N*P.

goal

fact(3,Res),write(" Факториал 3= " , Res),nl.

Действия при выполнении программы по шагам представлены в табл. 24.1.

Таблица 24.1

Действия при выполнении программы

Вызов предиката	Подстановки	Вычисления	Хвостовые вычисления	Результаты вычислений
fact(3,Res)	N=3, Res=R,	Next_N=N-1=2	R=N*P	Res=R=3*2=6
fact(2,P)	N'=2, P=R'	Next_N'=N'-1=2	R'=N'P'	P=R'=2*1=3
fact(1,F)	1=1, P'=1

<
/p> На первом шаге выполняется целевой запрос fact(3,Res) и выбирается первый вариант решения: правило fact( 1,1):-!, сопоставление для него заканчивается неуспехом, так как 3#1, происходит откат и выбирается второе правило. Для него сопоставление с заголовком правила заканчивается успешно, при этом выполняется подстановка N=3, Res=R, тело правила помещается в стек и начинают отрабатываться предикаты тела. Первый из них - сравнение Next_N=N-1, оно завершается успешно, переменная Next_N становится равной 2.

Затем инициируется вызов fact(2,P), снова выбирается первый вариант правила, сопоставление 1 #2 приводит к неуспеху, происходит откат и выбор второго варианта правила. Здесь сопоставление с заголовком правила заканчивается успешно, при этом выполняется подстановка N'=2, P'=R', новая копия правила помещается в стек и начинается его выполнение. Первое из них - сравнение Next_N'=N'-1 - завершается успешно, копия переменной Next_N' становится равной 2-1 =1.

Затем выполняется вызов fact(1,P'). Снова производится сопоставление с первым вариантом, и вот здесь оно становится успешным, подстановка имеет вид 1=1, Р'=1, тело первого правила пусто, поэтому никаких действий не инициирует и начинается выполнение "хвостов", оставшихся в стеке от копий второго правила, в результате этих вычислений переменная Res получит значение, равное 6, которое и будет выведено на экран следующим предикатом запроса write("Факториал 3= ", Res). Отметим, что в первом утверждении применено отсечение !. Сделано это для того, чтобы в случае использования внешнего запроса вида fасt(1 ,Res), т.е. запроса на вычисление факториала 1, после успешного сопоставления запроса с первым утверждением (1 = 1,Res=1) отсечь второй вариант правила для нахождения альтернативного решения. Если этого не сделать, то второе правило приведет к зацикливанию и ошибке. Для обеспечения корректной работы программы для запроса fact(0, Res) в раздел clauses нужно добавить еще одно утверждение, а именно fact(0,1):-!.

318

317 :: 318 :: Содержание

Содержание раздела