Логическое программирование на языке Visual Prolog. Солдатова О.П - 44 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

44
Рассмотрим специальный случай, когда процедура может вызвать себя
без сохранения информации о своем состоянии.
Предположим, что процедура вызывается последний раз, то есть после
вызванной копии, вызывающая процедура не возобновит свою работу, при
этом стек вызывающей процедуры должен быть заменен стеком вызванной
копии. Тогда аргументам процедуры просто присваиваются новые значения,
и
выполнение возвращается на начало вызывающей процедуры. С
процедурной точки зрения этот процесс напоминает обновление
управляющих переменных в цикле.
Эта операция в Visual Prolog называется оптимизацией хвостовой
рекурсии или оптимизацией последнего вызова.
Создание хвостовой рекурсии в программе на Прологе означает, что:
• вызов рекурсивной процедуры является самой последней
посылкой в правой части правила;
• до вызова рекурсивной процедуры в правой части правила не
было точек отката.
Приведем примеры хвостовой рекурсии.
Пример 42: рекурсивный счетчик с оптимизированной хвостовой
рекурсией.
count(100).
count(N):-write(N),nl,N1=N+1,count(N1).
goal
nl, count(0).
Модифицируем этот пример так, чтобы хвостовой рекурсии не
стало.
Пример 43: рекурсивный счетчик без хвостовой рекурсии.
count1(100).
count1(N):-write(N),N1=N+1,count1(N1),nl.
goal
nl, count1(0).
Из-за вызова предиката nl после вызова рекурсивного
предиката
должен сохраняться стек.
Пример 44: рекурсивный счетчик без хвостовой рекурсии.
count2(100).
count2(N):-write(N),nl,N1=N+1,count2(N1).
count2(N):-N<0, write(“N – отрицательное число“).
goal
nl, count2(0).
Здесь есть непроверенная альтернатива до вызова рекурсивного
предиката (третье правило), которое должно проверяться, если второе
правило завершится неудачно. Таким образом, стек должен быть сохранен.
Пример 45: рекурсивный счетчик без хвостовой рекурсии.
count3(100).
count3(N):-write(N),nl,N1=N+1,check(N1),count3(N1).

Страницы