Лабораторная работа №4
ТЕМА: Рекурсия.
ЦЕЛЬ: Научиться использовать возможности Пролога при организации повторяющихся действий.
Теоретическая часть
1. Итерация и рекурсия
Рассмотрим сначала организацию циклической обработки, а затем рекурсивные структуры данных.
Пролог реализует только два типа повторяющихся действий: бэктрекинг и рекурсию. В следующей части программы показано использование бэктрекинга для реализации цикла. На поставленный запрос будут выводится все возможные решения.
Clauses
country(england).
country(france).
country(germany).
country(denmark).
print_countries:-country(X),
write(X), % печать значения Х
nl, % перевод курсора на новую строку
fail.
print_countries.
Первая фраза говорит: «Найдя решение для предиката country(X), вывести страну X и перейти на новую строку». Затем вызывается предикат fail. В данном случае fail означает: если для поставленной цели могут быть найдены альтернативные решения, то вернуться и найти их.
Встроенный предикат fail всегда имеет ложное значение. Однако мы могли бы форсировать бэктрекинг, используя какой-нибудь другой, всегда ложный предикат типа 10=3+4 или country(abracadabra) (проверьте данное утверждение, заменив в своей программе fail на один из указанных предикатов).
Таким образом, будут получены все страны, и процесс обработки системой первой фразы завершиться. После этого начнётся обработка другой фразы того же предиката print_countries. Она ничего не делает, а только завершает успехом работу системы. Получите конечный вывод решения. Чем он отличается от вывода, если из программы убрать последнюю фразу print_countries?
Для наглядности в рассматриваемую программу можно внести следующие изменения:
-
напечатать заголовок;
-
напечатать все возможные решения запроса;
-
напечатать в конце заключительную фразу.
Тогда нужно модифицировать описание предиката print_countries.
print_countries:-write(“Some delightful places to live are:”), nl, fail.
print_countries:-country(X), write(X), nl, fail.
print_countries:-write(“And may be some others…”), nl.
Нужно ли теперь писать в конце фразу print_countries как факт? Почему?
Рассмотрим следующий предикат : repeat.
repeat:-repeat.
Такой трюк позволяет реализовать управляющую структуру, которая позволяет получить бесконечное число развязок. Более детально её работу понять после изучения понятия ''хвостовая рекурсия''. Для примера рассмотрим следующую программу:
clauses
repeat.
repeat:-repeat.
typewriter:- repeat,
readchar(C),
write(C),
char_int(C,13).
Эта программа показывает, как работает repeat. Правило typewriter… описывает процедуру, которая воспринимает символы с клавиатуры и печатает их на экране, пока не будет нажата клавиша ENTER (ASCII код = 13).
Она работает следующим образом:
-
Выполняется repeat (который ничего не делает).
-
Потом считывается символ в переменную С.
-
Затем печатается значение С.
-
Потом проверяется, не имеет ли С значение 13 в коде ASCII.
-
Если это так, программа завершается. Иначе начинается бэктрекинг и пересмотр альтернатив. Ни write, ни readchar не генерируют альтернативных развязок, поэтому бэктрекинг идёт до repeat, который позволяет получить альтернативные развязки.
-
Теперь обработка может вернуться в начало, считывать другой символ, печатать его, проверять на равенство 13.
Другой путь реализации повторений – это использование рекурсии. Рассмотрим рекурсивную программу вычисления значения факториала n!, которую можно интерпретировать следующим образом. Если n=1, то n!=1 (запишем factorial(1,1):-!), иначе n!=n*(n-1). Последнее вычисление обеспечивается следующей фразой определения factorial(Х,FactX).
factorial(1,1):-!.
factorial(Х,FactX):-Y=X-1,
factorial(Y,FactY),
FactX=X*FactY.
Предыдущая рекурсивная программа вычисления факториала может быть описана на Паскале в следующем итерационном виде:
p:=;
for i:=1 to n do
p:=p*I;
FacN:=p;
Или же используя цикл while:
p:=1;
i:=1;
while i<=n do
begin
p:=p*i;
i:=i+1
end;
FacN:=p;