3.3. Рекурсивные вычисления в Пролог-программе

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

• правая рекурсия − pr1( ) :- pr11( ), pr12( ), ... , pr1N( ), pr1( ).

• левая рекурсия − pr1( ) :- pr1(1), pr21( ), pr22( ), ... , pr2M( ).

• обобщенная рекурсия − pr1( ) :- pr11( ), pr12( ), ... , pr1N( ), pr1( ), pr21( ), pr22( ), … , pr2M( ).

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

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

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

Предикаты pr21( ), … , pr2M( ) не влияют на выполнение рекурсии, а выполняются только после выхода из нее. Эти предикаты получают значения переменных из стека, в который они помещаются на время выполнения рекурсии. Производимые при этом вычисления называют хвостовыми вычислениями. Идеи реализации рекурсивных вычислений представлены в примере и в табл. 3.1, составленной на основе соответствующей Пролог-программы.

Пример.

domains

number, product = integer

goal

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

clauses

fact (1, 1) :- !.

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

fact (Next_N, P) :- R = N * P.

Таблица 3.1.