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

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

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, потому что

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