Рекурсия – это второе средство для организации повторяющихся действий в Прологе. Рекурсивная процедура – это процедура, вызывающая сама себя до тех пор, пока не будет соблюдено некоторое условие, которое остановит рекурсию. Такое условие называют граничным.
Примером рекурсивных вычислений является известный алгоритм вычисления факториала. Факториал числа N определяется согласно алгоритму:
- 1!=1
- N!=N*(N-1)!
Реализация этого алгоритма на языке Пролог имеет такой вид:
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). % Пример вычисления 8!
При каждом вызове дизъюнкта factorial генерируются новые переменные, которые действуют всегда только на своем уровне вложенности, пока не встретится условие прекращения вычислений (базис рекурсии). Только после этого на обратном пути прохождения рекурсии определяются результаты.
Считается, что используется хвостовая рекурсия, если последнее условие в последнем правиле является рекурсивным. Такая рекурсия имеет преимущество перед нехвостовой рекурсией, так как позволяет ограничить рост стека и строго контролировать процесс возврата. По сути, хвостовая рекурсия – это итеративный процесс. В приведенном примере вычисления факториала рекурсия нехвостовая, а отношения above в рассмотренном выше примере – хвостовая.
Вычисление частичных сумм рядов
Списки в турбопрологе
Список ─ последовательность из произвольного числа элементов. Элементы списка разделяются запятыми и заключаются в квадратные скобки. Любой список представляет собой:
· либо пустой список (атом []);
· либо непустой список ─ структуру, состоящую из двух
частей: первый элемент ─ голова (Head) списка; второй
элемент ─ хвост (Tail) списка.
В общем случае голова списка может быть любым объектом языка Пролог, а хвост ─ обязательно должен быть списком. Поскольку хвост ─ список, то он либо пуст, либо имеет свои собственные голову и хвост. Для повышения наглядности программ в Прологе предусматриваются специальные средства для списковой нотации, позволяющие представлять списки в виде
[ Элемент1, Элемент2,...]
или
[ Голова | Хвост ]
или
[ Элемент1, Элемент2,... | Остальные].
Примерами списков могут служить:
[1,2,3,6,9,3,4]
[3.2,4.6,1.1,2.64,100.2]
["Вчера","Сегодня","Завтра"]
Количество элементов в списке называется его длиной. Список, не содержащий элементов, называется пустым или нулевым списком. Он обозначается так: []. Непустой список можно рассматривать как состоящий из двух частей: первый элемент списка ─ его голова, и остальная часть списка ─ хвост. Голова является элементом списка, хвост есть список сам по себе. Турбо-Пролог позволяет, в частности, выполнять над списками следующие операции: доступ к элементам списка, проверку на принадлежность к списку, сортировку элементов списка в порядке возрастания или убывания.
Если требуется включить в список элементы, относящиеся к разным типам данных (в том числе и к типу список), то нужно определить домен с альтернативами объектов разного типа, например, следующим образом:
domains
item = c (char); i (integer); s (string) /* c, i, s – функторыпредикатов */
item _list = item* /* домен списков смешанного типа */
predicates
list (item _list)
clauses
list ([i (10), i (12), i (2000), s (“НГПУ – ИФМИЭО”), c (“N”)]).
Рассмотрим программу "Птицы"с использованием списков.
/* Программа: П т и ц ы. */
domains
bird_list = bird_name*
bird_name = symbol
predicates
birds(bird_list)
clauses
birds(["ласточка","синица","чиж","воробей"]).
Отличительной особенностью описания списка является наличие звездочки (*) после имени списка элементов. Так запись bird_name* указывает на то, что это описание списка, элементами которoго являются bird_name (птицы).
Описание в разделе domains, следовательно, может выглядеть либо как
bird_list = bird_name*
bird_name = symbol
либокак
bird_list = symbol*
В разделе описания предикатов predicates требуется присутствие имени предиката, а за ним заключенного в круглые скобки имени списка.
birds(bird_list)
Сам список присутствует в разделе утверждений clauses:
birds(["ласточка","синица","чиж","воробей"]).
Выполните программу со следующими внешними запросами:
birds(All).
birds([_,_,_,B]).
birds([B1,B2,_,_]).
В программе "Птицы" для получения доступа к элементам списков были использованы внешние целевые утверждения. Задание цели в виде birds(All) обеспечивало присваивание переменной All всего списка в целом. Напротив, цель birds([_,_,_,B]) позволила извлечь из списка лишь один элемент. В этом случае, требовалось точное знание числа элементов списка. Для работы со списками, длина которых заранее неизвестна, используется метод разделения списка на голову и хвост. Данный метод работает вне зависимости от длины списка, до тех пор, пока список не будет исчерпан. Операция деления списка на голову и хвост обозначается при помощи вертикальной черты (|):
[Head|Tail].
Head здесь является переменной для обозначения головы списка, переменная Tail обозначает хвост списка.
Программа "Голова - хвост" демонстрирует использование метода. Это ─ программа печати введенных пользователем списков целых чисел и символов.
Списки в лиспе
Язык функционального программирования Лисп (Lisp) был разработан в 1958 году Джоном МакКарти (JohnMcCarthy). Название Лисп (Lisp) происходит от Listprocessing (обработка списков). Основным фундаментальным типом данных в языке LISP является список. Название языка LISP образовано от "LIStProcessing" ("обработка списка").
Список рекурсивно определяется так:
Список::= NIL | (S ─ выражение. Список)
Согласно этому определению любой непустой список является точечной парой.
Приведем примеры списков:
(LISP Functionallanguage)
(5 6 (8 (9)) 23 NIL)
Важно выделить понятие пустого списка, который не содержит элементов, он обозначается () или атомом NIL. Например, (NIL ()) ─ список, состоящий из двух пустых списков. Оперативная память компьютера, на котором "работает" LISP, логически разбивается на маленькие области, которые называются списочными ячейками. Списочная ячейка состоит из полей с именами CAR и CDR, каждое из которых содержит указатель. Указатель может ссылаться на другую списочную ячейку или на другой объект языка LISP, например, на атом. Указатели между ячейками образуют как бы цепочку, по которой можно из предыдущей ячейки попасть в следующую и так, наконец, до атомарных объектов. Каждый атом, известный системе, записан в определенном месте памяти лишь один раз. Графически списочную ячейку будем представлять прямоугольником, разделенным на поля CAR и CDR. Указатель изображается в виде стрелки, начинающейся в одной из частей прямоугольника и заканчивающейся на изображении другой ячейки или атоме, на который ссылается указатель.
Пример 1. Изобразим список (A B C D) в графической нотации: