4. Организация повторов

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

БАЗИС РЕКУРСИИ - это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу даже без использования рекурсии.

ШАГ РЕКУРСИИ - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката. Если мы хотим избежать зацикливания, определяемый предикат должен вызываться не от тех же параметров, которые указаны в заголовке правила. Параметры должны изменяться на каждом шаге так, чтобы в итоге либо сработал базис рекурсии, либо условие выхода из рекурсии, размещенное в самом правиле.

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

НЕДОСТАТОК: может не хватать для работы стека. При каждом рекурсивном вызове предиката в специальном стековом фрейме запоминаются все промежуточные переменные, которые могут понадобиться. Максимальный размер стека при работе под управлением операционной системы MS DOS всего 64 Кб. Этого достаточно для размещения около трех-четырех тысяч стековых фреймов (в зависимости от количества и размера промежуточных переменных). При больших входных значениях стека может не хватить.

Есть, правда, один вариант рекурсии, который использует практически столько же оперативной памяти, сколько итерация в императивных языках программирования. Это так называемая хвостовая или правая рекурсия. Для ее осуществления рекурсивный вызов определяемого предиката должен быть последней подцелью в теле рекурсивного правила и к моменту рекурсивного вызова не должно остаться точек возврата (непроверенных альтернатив). То есть у подцелей, расположенных левее рекурсивного вызова определяемого предиката, не должно оставаться каких-то непроверенных вариантов и у процедуры не должно быть предложений, расположенных ниже рекурсивного правила.

5. Ветвление-выбор

6. Стандартные математические предикаты

.

.

7. СПИСКИ И ОПЕРАЦИИ НАД НИМИ (list = integer*)

Рекурсивное определение списка.

Список — это структура данных, определяемая следующим образом:

1. пустой список ([ ]) является списком;

2. структура вида [H|T] является списком, если H — первый элемент списка (или несколько первых элементов списка, перечисленных через запятую), а T — список, состоящий из оставшихся элементов исходного списка.

В императивных языках основной структурой данных являются массивы. В Прологе так же, как и в Лиспе, основным составным типом данных является список.

[] — пустой список, т.е. список, не содержащий элементов (в Лисп - nil).

Элементы списка могут быть любыми, в том числе и списками.

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

Операция "|" позволяет разделить список на хвост и голову (в Лиспе - car и cdr) или приписать объект (объекты) к началу списка (cons в Лиспе). Данное определение позволяет организовывать рекурсивную обработку списков, разделяя непустой список на голову и хвост.

Чтобы организовать обработку списка достаточно задать базис рекурсии (правило или факт, определяющее, что нужно делать с пустым списком), а также рекурсивное правило, устанавливающее порядок перехода от обработки всего непустого списка к обработке его хвоста.