Основы программирования на языке Пролог



         

Рекурсия


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

Начнем изучение рекурсии в Прологе с классического примера. Предположим, что в базе знаний есть набор фактов, описывающий родственные связи людей через отношение "быть родителем". Предикат родитель имеет два аргумента. В качестве его первого аргумента указывается имя родителя, в качестве второго - имя ребенка. Мы хотим создать отношение "быть предком", используя предикат родитель.

Для того чтобы один человек был предком другого человека, нужно, чтобы он либо был его родителем, либо являлся родителем другого его предка.

Запишем эту идею:

предок(Предок,Потомок):- родитель(Предок,Потомок). /* предком является родитель */ предок(Предок,Потомок):- родитель(Предок,Человек), предок(Человек,Потомок). /* предком является родитель предка */

Отношение предок является транзитивным замыканием отношения родитель, то есть это наименьшее отношение, включающее отношение родитель и обладающее свойством транзитивности. Напомним, что отношение называется транзитивным, если для любых пар (А,В) и (В,С), находящихся в этом отношении, пара (А,С) также находится в этом отношении.


Содержание    Вперед