Рекурсивные вычисления
Использование рекурсии обеспечивает организацию циклических вычислений в Прологе. Рекурсия применяется обычно в ситуациях, когда либо число возможных решений заранее не известно, либо когда обрабатываются структуры данных с произвольным числом элементов.
Рекурсивное описание правила содержит в своем теле ссылку на заголовок этого же правила. При этом возможны следующие варианты рекурсивных правил:
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 |