Программирование с накопителями

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

ПРОГРАММА 4.

Итеративное определение факториала (вариант 1).

factorial(N,FactN):- fact(N,FactN,1,1).

fact(N,FactN,I,P):- /* накопитель I - аналог счетчика */

I<N /* накопитель P – промежуточное значение факториала*/

I1 is I+1, /* - значение факториала */

P1 is P*I1,

fact(N,FactN,I1,P1).

fact(N,FactN,N,FactN).

ЗАДАНИЕ 3.3

Выполните программу 4 в режиме трассировки. Введите запрос:

?-factorial(3,F).

ПРОГРАММА 5.

Итеративное определение факториала (вариант 2, более эффективный).

factorial(N,FactN):- fact(N,FactN,1).

fact(N,FactN,P):-

N>0,

P1 is P*N,

N1 is N-1,

fact(N1,FactN,P1).

fact(0,FactN,FactN).

ЗАДАНИЕ 3.4

Выполните программу 5 в режиме трассировки. Введите запрос и нарисуйте для него дерево вывода:

?-factorial(4,F).

РЕКУРСИВНЫЕ ОБЪЕКТЫ

Другим типом рекурсии в Прологе является рекурсия по данным.

ПРОГРАММА 6.

Рекурсивное определение списка студентов.

/*группа номер 1,состоящая из студентов 'Шекспир','Мольер','Чехов'*/

kurs(1,gruppa('Шекспир',gruppa('Мольер',gruppa('Чехов',empty)))).

kurs(2,gruppa('Гильберт',gruppa('Эйлер',gruppa('Лейбниц',

gruppa('Кантор',empty))))).