Рекурсия в Турбо Прологе

Другим способом организации циклов является рекурсия, т.е. вызов предикатами самих себя. Рассмотрим вычисление значения N!    

Пример 3 - Вычисление факториала c использованием рекурсии.

predicates
%Значение факториала считается вещественным, чтобы избежать переполнения
factorial(integer, real)

clauses
/*         если N=1, то значение факториала равно 1  */
factorial(1, 1) :- !.  % условие останова рекурсии

/*    Во всех других случаях надо найти факториал N-1,
а затем умножить его на N  */
factorial(N, FactN) :-

/* Внимание!!! Оператора ПРИСВАИВАНИЯ нет!!!
Происходит связывание переменных N и NN   */
NN = N-1,

    /* рекурсивный вызов factorial c НОВЫМИ параметрами */
factorial(NN, FactNN),
FactN = N*FactNN.

Ecли теперь в диалоговом режиме выдать запрос

        Goal:factorial(3,F)

то в режиме ТРАССИРОВКИ будет получено решение F=6. Этот вариант не эффективен по памяти, так как требует запоминания ВСЕХ промежуточных переменных на КАЖДОМ шаге рекурсии в так называемом ФРЕЙМЕ СТЕКА и при достаточно большом значении N его может не хватить.

Выход из положения предоставляет ХВОСТОВАЯ рекурсия,которая организуется следующим образом:
-рекурсивный вызов должен быть ПОСЛЕДНЕЙ подцелью;
-нужно избавиться от точек возврата с помощью отсечения (предикат "!"), чтобы исключить возможные альтернативы.

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

Пример  Использование хвостовой рекурсии.

predicates
factorial(integer,real)
factorial(integer, real, integer, real)

clauses
factorial(N,FactN):-
factorial(N,FactN,1,1). % установка начальных значений

factorial(N, FactN, N, FactN):- !. % условие останова
factorial(N, FactN, I, P):-
NewI = I+1,
NewP = P*NewI,
factorial(N, FactN, NewI, NewP).