На этом шаге мы рассмотрим ипользование отката с петлями.
Поиск с возвратом является хорошим способом определить все возможные решения целевого утверждения. Но, даже если ваша задача не имеет множества решений, можно испопользовать поиск с возвратом для выполнения итераций. Просто определите предикат с двумя предложениями:
repeat.
repeat:-
repeat.
Этот прием демонстрирует создание структуры управления Пролога (программа pro39_1.pro), которая порождает бесконечное множество решений, а каким образом, - поймете позже, прочитав раздел о хвостовой рекурсии. Цель предиката repeat - допустить бесконечность поиска с возвратом (бесконечное количество откатов).
/*Ипользование repeat для сохранения введенных символов и печатать их до тех пор, пока пользователь не нажмет Tab (Табуляция).*/ predicates repeat typewriter clauses repeat. repeat:- repeat. typewriter:- repeat, readchar(C),% Читать символ, его значение присвоить С write(С), С = '\t',% Символ табуляция (Tab)? или неуспех !. goal typewriter () ,nl.
Программа pro39_1.pro показывает, как работает repeat. Правило typewriter:- описывает процесс приема символов с клавиатуры и отображения их на экране, пока пользователь не нажмет клавишу Tab.
Правило typewriter работает следующим образом:
- Выполняет repeat (который ничего не делает, но ставит точку отката).
- Присваивает переменной C значение символа.
- Отображает C.
- Проверяет, соответствует ли C коду табуляции.
- Если соответствует, то - завершение. Если нет - возвращается к точке отката и ищет альтернативы. Так как ни write, ни readchar не являются альтернативами, постоянно происходит возврат к repeat, который всегда имеет альтернативные решения.
- Теперь обработка снова продвигается вперед: считывает следующий символ, отображает его и проверяет на соответствие коду табуляции.
Заметьте, кстати, что C теряет свое значение после отката в позицию перед вызовом предиката readchar(С), который связывает переменную C. Такой тип освобождения переменной существенен, когда поиск с возвратом применяется для определения альтернативных решений целевого утверждения, но не эффективен при использовании поиска с возвратом в других целях. Смысл в том, что хотя поиск с возвратом и может повторять операции сколько угодно раз, он не способен "запомнить" что-либо из одного повторения для другого.
Замечание: Все переменные теряют свои значения, когда обработка откатывается в позицию, предшествующую тем вызовам предикатов, которые эти значения устанавливали.
Не существует простого способа сохранения значений счетчика числа повторений петли или любых других значений, вычисляемых при выполнении циклов повторения.
Рекурсивные процедуры
Другой способ организации повторений - рекурсия. Рекурсивная процедура - это процедура, которая вызывает сама себя. В рекурсивной процедуре нет проблемы запоминания результатов ее выполнения, потому что любые вычисленные значения можно передавать из одного вызова в другой как аргументы рекурсивно вызываемого предиката.
Логика рекурсии проста для осуществления. Забудьте на мгновение, что компьютер последовательно проходит ячейки памяти одну за другой, и представьте себе ЭВМ, способную "понять":
Найти факториал числа N:
Если N равно 1,то факториал равен 1
Иначе найти факториал N-1 и умножить его на N.
Этот подход означает следующее: чтобы найти факториал 3, вы должны найти факториал 2, а чтобы найти факториал 2, вы должны вычислить факториал 1. Вы можете найти факториал 1 без обращения к другим факториалам, поэтому повторения не начнутся. Если у вас есть факториал 1, то умножаете его на 2, чтобы получить факториал 2, а затем умножаете полученное на 3, чтобы получить факториал 3.
В Прологе это выглядит так:
factorial(1,1):-!.
factorial(X,FactX):-
factorial(Y,FactY),
Y=X-1,
factorial(Y,FactY),
FactX=X*FactY.
/*Рурсивная программа вычисления факториалов.
Рекурсия обычная, не хвостовая.*/
predicates
factorial(integer,real)
clauses
factorial(1,1):-!.
factorial(X, FactX) :-
Y=X-1,
factorial(Y,FactY),
FactX = X*FactY.
goal
factorial(X,FactX),
write(FactX).
Как компьютер выполняет предикат factorial в середине обработки предиката factorial? Если вы вызываете factorial с Х=3, то factorial обратится к себе с Х=2. Будет ли тогда Х иметь два значения, или второе значение затирает первое, или...?
Дело в том, что компьютер создает новую копию предиката factorial таким образом, что factorial становится способным вызывать сам себя как полностью самостоятельную процедуру. При этом, конечно, код выполнения не будет копироваться, но все аргументы и промежуточные переменные копируются.
Информация хранится в области памяти, называемой стековым фреймом (stack frame) или просто стеком (stack), который создается каждый раз при вызове правила, когда выполнение правила завершается, занятая его стековым фреймом память овобождается (если это не недетерминированный откат), и выполнение продолжается в стековом фрейме правила-родителя.
Преимущества рекурсии
Рекурсия имеет три основных преимущества:
- она может выражать алгоритмы, которые нельзя удобно выразить никаким другим образом;
- она логически проще метода итерации;
- она широко используется в обработке списков.
Рекурсия - хороший способ для описания задач, содержащих в себе подзадачу такого же типа. Например, рекурсивная сортировка (для сортировки списка, он разделяется на части, части сортируются и затем объединяются вместе).
Логически рекурсивным алгоритмам присуща структура индуктивного математического доказательства. Приведенная выше рекурсивная программа вычисления факториала pro39_2.pro описывает бесконечное множество различных вычислений с помощью всего лишь двух предложений. Это позволяет легко увидеть правильность этих предложений. Кроме того, правильность каждого предложения может быть изучена независимо от другого.
На следующем шаге мы начнем рассматривать оптимизацию хвостовой рекурсии.
