2015-04-01
234
predicates
count(integer)
check(integerl)
clauses
count(N):-
write(N),
NewN=N+1,
сheck(NewN),
count(NewN),
nl.
check(Z):-
Z<5.
Из-за наличия nl вызов процедуры count() перестал быть последним шагом, стек придется сохранить, чтобы обработку можно было вернуть к вызывающей процедуре.
Еще один случай не хвостовой рекурсии:
Листинг 5.12.Пример не хвостовой рекурсии за счет использования недетерминированного предиката
check_determ
predicates
count(integer)
check(integer)
clauses
count(N):-
write(N),nl,
NewN=N+1,
сheck(NewN),
count(NewN).
count(N).
check(Z):- Z<5.
Добавили второй count(N). Получили недетерминированный предикат. Этот предикат еще не проверен к моменту выполнения рекурсивного вызова, поэтому стек должен быть сохранен, так как в случае неуспеха рекурсивного вызова процедура может откатиться и начать проверку этой альтернативы.
Замечания:
- Если проверку chеck(NewN) не поставить, то предыдущие программы будут работать до истощения памяти.
- Непроверенные альтернативы не обязательно должны быть отдельными предложениями рекурсивной процедуры. Они могут находиться в любом вызываемом предикате. Например,
......
check(NewN),
........
check(Z):-Z>=0.
check(Z):-Z<0.
Eсли Z>0,то первое check(Z) достигло цели, а второе в этот момент еще не проверено, поэтому предикат count() должен сохранить свои стековые копии, чтобы иметь возможность вернуться и начать проверку второго предложения, если рекурсивный вызов будет неудачен.
Для поиска недетерминированных предложений используйте директиву check_determ.
Для удаления альтернативных вызовов используйте cut, достигнув которого можно больше не обращать внимание на альтернативные предложения, а раз так, то и стек хранить не надо, и рекурсивный вызов может свободно идти дальше. Если отсечение выполнено, то компьютер считает, что непроверенных альтернатив больше нет, и не создает стекового фрейма.
Пример программы, которая циклически считывает символ, введенный пользователем. Если символ не равен #, то он выводится на экран, иначе процесс заканчивается.
Листинг 5.13. Использование рекурсии для циклического считывания символов
domains
char_data=char
predicates
write_prompt
read_a_character
goal
clearwindow,
write_prompt,
read_a_character.
clauses
write_prompt:-
write(“введи символ”),nl,
write(“окончание по #”),nl,nl.
read_a_character:-
readchar(Char_data),
Char_data<>’#’,
write(Char_data),
read_a_character.
