Повторение и рекурсия. Откат

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

Используются следующие методы повторения:

· метод отката после неудачи;

· метод отсечения и отката;

· правило повтора, определяемое пользователем;

· обобщенное рекурсивное правило.

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

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

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

· повторение;

· рекурсия.

Правила Пролога, выполняющие повторения, используют откат, а правила, выполняющие рекурсию используют самовызов.

Формат правила, выполняющего повторение:

repetitive_rule :- /* правило повторения */

<предикаты и правила>,

fail. /* неудача */

Конструкция <предикаты и правила> в теле правила обозначает предикаты, содержащие несколько утверждений, а так же правила, определенные в программе. Встроенный предикат fail (неудача) вызывает откат, так что предикаты и правила выполняются еще раз.

Формат правила, выполняющего рекурсию:

recursive_rule :-/* правило рекурсии */

<предикаты и правила>,

recursive_rule.

Последним правилом в теле данного правила является само правило recursive_rule. Правила рекурсии содержат в теле правила сами себя.

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

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