Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Методичка по Прологу.doc
Скачиваний:
68
Добавлен:
01.05.2014
Размер:
501.25 Кб
Скачать

3.2. Рекурсии

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

6. Примером рекурсивных вычислений является известный алгоритм вычисления факториала. Hа Прологе эта программа может иметь такой вид:

Domains

N, F=real

Predicates

factorial(N,F)

Clauses

factorial(1,1). % база рекурсии, ограничение вычислений

factorial(N,R):– N>0, N1=N-1,

factorial(N1,R1), R=R1*N.

Goal

factorial(8,F),write(F).

При каждом вызове дизъюнкта factorialгенерируются новые переменные, которые действуют всегда только на своем уровне вложенности, пока не встретится условие прекращения вычислений. Только после этого на обратном пути прохождения рекурсии определяются результаты, которые передаются вверх.

Любое рекурсивное определение содержит по крайней мере одно нерекурсивное правило и одно или несколько правил с рекурсией. В большинстве случаев имеется по одному правилу каждого типа. Считается, что используется хвостовая рекурсия, если последнее условие в последнем правиле является рекурсивным. Такая рекурсия имеет преимущество перед нехвостовой рекурсией, так как позволяет ограничить рост стека и строго контролировать процесс возврата. Это происходит благодаря очистке стека после успешного сопоставления условия, содержащего рекурсию.

3.3. Программирование циклов

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

7. Рекурсивный цикл со счетчиком. Цикл выполнится 10 раз.

for(10).

for(N):– N<10,

prosess,

N1=N+1,

for(N1).

Goal for(0).

8. Бесконечный рекурсивный цикл. Выполняется ввод и печать символов. Процесс повторяется до нажатия клавиши ENTER, имеющей кодовое число 13.

typewr('\13').

typewr(Char):–write(Char),

readchar(C),

typewr(C).

Goal readchar(Char), typewr(Char).

9. Использование бэктрекинга для перебора всех вариантов. Пусть есть фрагмент программы

fact(f1).

fact(f2).

fact(f3).

print_fact:– fact(X), write(X), fail.

print_fact.

Наличие второго клоза предиката print_factпозволяет всей программе завершиться успешно после печати всех фактов.

10. Большую группу примеров циклов можно продемонстрировать с использованием предиката repeat. Этот предикат программируется следующим образом:

repeat.

repeat:–repeat.

Repeat– это цель, которая всегда успешна. Она недетерминирована, это означает: что всякий раз, когда до нее доходит перебор, порождается новая ветвь вычислений.

Пример цикла с сочетанием repeatиfail.

run:– repeat,

readln(X),

prosess(X,Y),

write(Y),

fail.

Предикат failзаставляет систему осуществлять возврат кrepeatиprosessв случае успешного завершения.

Можно также использовать сочетание repeatи стандартного предикатаkeypressed(вместоrepeatfail) или сочетаниеnot(keypressed) и рекурсии:

run:– repeat, prosess,

keypråssed.

run:– not(keypressed),

prosess, run.

С использованием предиката repeatможно также организовать любое подходящее условие окончания работы цикла:

run:– repeat,

prosess,

write("Будет еще ввод?(y/n)" ),

readchar(Ans), Ans = 'n'.