Основы современных компьютерных технологий


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


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

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

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      
<


Начало  Назад  Вперед