Как задать хвостовую рекурсию

Что означает фраза "одна процедура вызывает другую, выполняя свой

самый последний шаг"? На языке Пролог это значит:

1. Вызов является самой последней подцелью предложения.

2. Ранее в предложении не было возвратных точек.

Ниже приводится удовлетворяющий обоим условиям пример:

count(N) :-

write(N), nl,

NewN = N+1,

count(NewN).

Эта процедура является хвостовой рекурсией, которая вызывает себя

без резервирования нового стека, и поэтому не истощает запас своей памя-

ти. Как показывает программа CH07EX04.PRO, если вы дадите ей целевое ут-

верждение

count(0)

то предикат count будет печатать целые числа начиная с 0 и никогда не ос-

тановится. В конечном счете, ошибки округления приведут к печати неточных

чисел, но остановки не произойдет.

/* Программа CH07EX04.PRO */

Программа с хвостовой рекурсией, которая не истощает память.

predicates

count(real)

/* Вещественые типы могут быть значительно больше

целых чисел */

clauses

count(N) :-

write(N), nl,

NewN = N+1,

count(NewN).

goal

count(1).

Упражение

Не заглядывая вперед, преобразуйте программу CH07EX04.PRO, так чтобы

не было больше хвостовой рекурсии. Сколько итераций может она выполнить

до истощения своей памяти? Попробуйте и посмотрите. (Помните, что число

возможных итераций зависит от размера стека. Чтобы изменить этот размер

вы можете ввести в программу директиву компилятора стека или выбрать

О/С/Memory Allocation/Stack из системных меню.)

Как избежать хвостовой рекурсии

Только что был продемонстрирован вызов хвостовой рекурсии. Программа

CH07EX05.PRO показывает три ошибочных способа хвостовой рекурсии.

1. Если рекурсивный вызов не самый последний шаг, процедура не явля-

ется хвостовой рекурсией:

badcount1(X) :-

write(X), nl,

NewX = X+1,

badcount1(NewX),

nl.

Каждый раз badcount1 вызывает себя, стек должен быть сохранен для

того, чтобы обработку можно было вернуть к вызывающей процедуре, ко-

торая должна выполняться до nl. Поэтому, пока программа исчерпает

запас своей памяти, она сделает всего несколько тысяч рекурсивных

вызовов.

2. Другой способ остановить хвостовую рекурсию - оставить альтерна-

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

стек должен быть сохранен как в случае неудачного завершения рекур-

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

тернативу. Например:

badcount2(X) :-

write(X), nl,

NewX = X+1,

badcount2(NewX).

badcount2(X) :-

X < 0,

write("X is negative.").

Здесь первое предложение badcount2 вызывает себя, когда второе пред-

ложение еще не выполнено. Снова программа истощает память после оп-

ределенного количества вызовов.

3. Для остановки хвостовой рекурсии не обязательно иметь рекурсивную

процедуру отдельным предложением. Непроверенная альтернатива может

также быть и в других вызываемых предложениях. Например:

badcount3(X) :-

write(X), nl,

NewX = X+1,

check(NewX),

badcount3(NewX).

check(Z) :- Z >= 0.

check(Z) :- Z < 0.

Предположим, что Х положительная, как это обычно бывает. Тогда, ког-

да badcount3 вызывает себя, первое предложение check достигает цели,

а второе предложение check еще не выполнено. Поэтому, badcount3 сох-

раняет свой стек неизменным, чтобы вернуться и выполнить второе

предложение check, как будто рекурсивный вызов завершился неудачно.

/* Программа CH07EX05.PRO */

/*Три процедуры похожие на процедуры CH07EX04.PRO, но без хвостовой

рекурсии. Они истощают запас своей памяти через несколько сотен итера-

ций.*/

predicates

badcount1(real)

badcount2(real)

badcount3(real)

check(real)

clauses

/* badcount1:

Рекурсивный вызов - не последний шаг.*/

badcount1(X) :-

write(X), nl,

NewX = X+1,

badcount1(NewX),

nl.

/* badcount2:

Предложение не выполняется во время осуществления рекур-

сивного вызова. */

badcount2(X) :-

write(X), nl,

NewX = X+1,

badcount2(NewX).

badcount2(X) :-

X < 0,

write("X is negative.").

/* badcount3:

Непроверенная альтернатива в процедуре, вызванной перед

рекурсивным вызовом. */

badcount3(X) :-

write(X), nl,

NewX = X+1,

check(NewX),

badcount1(NewX).

check(Z) :- Z >= 0.

check(Z) :- Z > 0.

Заметьте, что badcount2 и badcount3 хуже, чем badcount1, потому что

они образуют возвратные точки.