Clauses

fact(0,1):-!.

fact(K,F):- K1=K-1, fact(K1,F1), F=F1*K.

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

-оценивается первое утверждение в рекурсивном определении;

-если первое утверждение не выполняется, осуществляется переход к следующему в определении утверждению, и оно оценивается. Обычно это правило, которое содержит условие, начинающее рекурсию;

-после прохождения первого уровня рекурсии выполнение возвращается к первому утверждению в определении, и опять оценивается его истинность;

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

Различают два стиля в определении рекурсивных определений:

Нисходящая рекурсия

Описание процесса начинается с конца, с момента N, и номер шага постепенно уменьшается на 1.

В качестве правила остановки выбираются начальные условия. Условия окончания используются как значения аргументов целевого утверждения-запроса, например fact(4,Х).

Пример. Вычисление чисел Фибоначчи: F₁=1, F₂=2, F_n=F_n-1+_Fn-2.

Predicates

Fib(integer,integer)

Clauses

fib(0,0):-!.

fib(1,1):-!.

fib(K,F):- K1=K-1, fib(K1,F1), K2=K-2, fib(K2,F2), F=F1+F2.