57 (1006277), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

будет соответствовать оператору if <условие> then P else P2, то есть если условие имеет место, то выполнить P, иначе выполнить P2. Например, в случае с максимумом, можно расшифровать нашу процедуру как "если X>Y, то M=X, иначе M=Y".

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

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

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

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

предок(Предок,Потомок):-

родитель(Предок,Потомок).

/* предком является родитель */

предок(Предок,Потомок):-

родитель(Предок,Человек),

предок(Человек,Потомок).

/* предком является родитель предка */

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

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

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

Шаг рекурсии - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката. Если мы хотим избежать зацикливания, определяемый предикат должен вызываться не от тех же параметров, которые указаны в заголовке правила. Параметры должны изменяться на каждом шаге так, чтобы в итоге либо сработал базис рекурсии, либо условие выхода из рекурсии, размещенное в самом правиле. В общем виде правило, реализующее шаг рекурсии, будет выглядеть так:

<имя определяемого предиката>:-

[<подцели>],

[<условие выхода из рекурсии>],

[<подцели>],

<имя определяемого предиката>,

[<подцели>].

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

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

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

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

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

Характеристики

Список файлов ответов (шпаргалок)