domains
number=integer
predicates
write_number(number)
goal
clearwindow,
write(“ вот числа”),nl,nl,
write_number(1),nl,nl,
write(“all done,bye”).
clauses
write_number(8).
write_number(Number):-
Number<8,
write(“ “,Number),nl,
next_number=Number+1,
write_number(Next_number).
Подумайте, что надо изменить в программе для выдачи на экран чисел в обратном порядке.
Листинг 5.15. Рекурсивная программа вычисления факториала
trace
predicates
factorial(integer,real)
clauses
factorial(1,1):-!.
factorial(X,FactX):-
Y=X-1,
factorial(Y,FactY),
FactX=X*FactY.
goal
clearwindow,
write("input X-integer\n"),
readint(X),
factorial(X,FactX),
write("X=",X," FactX=",FactX).
Измените программу таким образом, чтобы рекурсия стала хвостовой.
Замечание: ПК создает новую копию предиката factorial таким образом, что factorial становится способным вызывать сам себя как полностью самостоятельную процедуру. При этом код выполнения не будет, конечно, копироваться, но все аргументы и промежуточные переменные копируются.
Информация хранится в стеке, который создается каждый раз при вызове правила. Когда выполнение правила завершится, стек освободится (если это не недетерминированный откат), и выполнение продолжается в стеке правила-родителя.
|
|
Выводы
· Prolog имеет два способа повторения циклических участков программы – поиск с возвратом и рекурсию.
· Поиск с возвратом – это мощное средство с точки зрения использования памяти, но после каждой итерации переменные обновляют свои значения, при этом их старые значения теряются.
· Рекурсия позволяет сохранять значения переменных, но она не эффективна с точки зрения требуемого объема памяти. Однако, есть хвостовая рекурсия, и Prolog способен ее оптимизировать, то есть снять требования к объему памяти. Для этого рекурсивный вызов должен быть последней подцелью в теле предложения, а тело предложения и рекурсивный предикат должны быть детерминированными.
· В Prolog’е рекурсивным может быть не только предложение, но и структуры данных. Prolog в отличие от большинства других языков позволяет определять типы рекурсивных данных, в которых указатели создаются и обрабатываются автоматически. Тип данных является рекурсивным, если он допускает структуры, содержащие такие же структуры, как и они сами. Такими структурами являются, например, список, дерево и др. Каждая ветвь дерева сама является деревом, поэтому структура рекурсивна. В Prolog’е мы имеем собственно рекурсивную структуру дерева, а не представление дерева в памяти, как это было в С и С++.