Логическое программирование на языке Visual Prolog. Солдатова О.П - 43 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

43
Например, в приведенной ниже программе вычисления факториала
(пример 48), приведен пример написания рекурсивного предиката. При этом
Пролог создает новую копию предиката factorial таким образом, что он
становится способным вызвать сам себя как самостоятельную процедуру.
При этом не происходит копирования кода выполнения, но все
аргументы и промежуточные переменные копируются в стек,
который
создается каждый раз при вызове рекурсивного правила.
Когда выполнение правила завершается, занятая стеком память
освобождается и выполнение продолжается в стеке правила-родителя.
Пример 40: написать программу вычисления факториала.
predicates
factorial (byte, word)
clauses
factorial (0, 1).
factorial (1, 1):-!.
factorial (N, R):- N1=N-1, factorial (N1, R1), R=N*R1.
goal
f (7, Result).
Для вычисления факториала используется последовательное
вычисление произведения ряда чисел. Его значение образуется после
извлечения значений соответствующих переменных из стека, используемых
как список параметров для последнего предиката в теле правила. Этот
последний предикат вызывается после завершения рекурсии.
Пример 41: написать программу, генерирующую числа Фибоначчи до
заданного значения.
predicates
f (byte, word)
clauses
f (1, 1).
f (2, 1).
f(N, F):- N1=N-1, f (N1, F1), N2=N1-1, f (N2,F2), F=F1+F2.
goal
f (10, Fib).
У рекурсии есть три основных преимущества:
• логическая простота по сравнению с итерацией;
• широкое применение при обработке списков;
• возможность моделирования
алгоритмов, которые нельзя
эффективно выразить никаким другим способом (например,
описания задач, содержащих в себе подзадачи такого же типа).
У рекурсии есть один большой недостаток – использование большого
объема памяти. Всякий раз, когда одна процедура вызывает другую,
информация о выполнении вызывающей процедуры должна быть сохранена
для того, чтобы вызывающая процедура могла, после
завершения вызванной
процедуры, возобновить выполнение на том месте, где остановилась.

Страницы