ИТЕРАЦИЯ И РЕКУРСИЯ

Рассмотрим сначала организацию циклической обработки, а затем рекурсивные структуры данных.

Пролог реализует только два типа повторяющихся действий: бэктрекинг и рекурсию. В следующей части программы показано использование бэктрекинга для реализации цикла. На поставленный запрос будут выводится все возможные решения.

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?

Для наглядности в рассматриваемую программу можно внести следующие изменения:

1. напечатать заголовок;
2. напечатать все возможные решения запроса;
3. напечатать в конце заключительную фразу.

Тогда нужно модифицировать описание предиката 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).

Она работает следующим образом:

1. Выполняется repeat (который ничего не делает).
2. Потом считывается символ в переменную С.
3. Затем печатается значение С.
4. Потом проверяется, не имеет ли С значение 13 в коде ASCII.
5. Если это так, программа завершается. Иначе начинается бэктрекинг и пересмотр альтернатив. Ни write, ни readchar не генерируют альтернативных развязок, поэтому бэктрекинг идёт до repeat, который позволяет получить альтернативные развязки.
6. Теперь обработка может вернуться в начало, считывать другой символ, печатать его, проверять на равенство 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;