BD_Zadania_dlya_4_kursa_Povtorenie_i_rekursia-1..

Повторение и рекурсия
Давайте создадим предикат, который будет находить максимум из двух чисел. У предиката будет три аргумента. Первые два аргумента - входные для исходных чисел, в третий выходной аргумент  будет помещен максимум  из первых двух аргументов.
Предикат  будет довольно простым. Мы запишем, что в случае, если первое число больше второго, максимальным будет первое число, в случае, если первое число меньше, максимумом будет второе число. Надо также не забыть про ситуацию, когда числа равны, в этом случае максимумом будет любое из них.
Решение можно записать в следующем виде:
max(X,Y,X):-
X>Y. /* если первое число больше второго,
то первое число - максимум */
max(X,Y,Y):-
X то второе число - максимум */
max(X,Y,Y):-
X=Y. /* если первое число равно второму,
возьмем в качестве максимума
второе число */
Первое предложение  можно объединить со вторым или третьим в одно предложение. Тогда процедура будет состоять не из трех предложений, а всего из двух:
max(X,Y,X):-
X>Y. /* если первое число больше второго,
то первое число - максимум */
max(X,Y,Y):-
X<=Y./* если первое число меньше или равно
второму, возьмем в качестве максимума
второе число */
Однако полученная процедура еще далека от совершенства. С одной стороны, в случае, когда первое проверяемое условие (X>Y ) не выполнено, будет проверяться второе условие ( X<=Y ), хотя понятно, что если не выполнено X>Y, значит X<=Y. С другой стороны, в случае, если первое условие имело место и первое число оказалось больше второго, Пролог-система свяжет третий аргумент предиката max с первым аргументом, после чего попытается сопоставить второе предложение. Хотя нам очевидно, что после того, как максимум определен, не нужно больше ничего делать. Других вариантов в данной ситуации просто не может быть. И, значит, проверка второго условия избыточна.
В данной ситуации нам пригодится встроенный предикат, который по-английски называется cut, по-русски - отсечение, а в программе на Прологе он обозначается восклицательным знаком " !". Этот предикат предназначен для ограничения пространства поиска, с целью повышения эффективности работы программ. Он всегда завершается успешно. После того, как до него дошла очередь, он устанавливает "забор", который не дает "откатиться назад", чтобы выбрать альтернативные решения для уже "сработавших" подцелей. То есть для тех, которые расположены левее отсечения. На цели, расположенные правее, отсечение не влияет. Кроме того, отсечение отбрасывает все предложения процедуры, расположенные после предложения, в котором находится отсечение .
С использованием отсечения наше решение будет еще короче:
max2(X,Y,X):-
X>Y,!./* если первое число больше второго,
то первое число - максимум */
max2(_,Y,Y). /* в противном случае максимумом будет
второе число */
В случае, если сработает отсечение, а это возможно, только если окажется истинным условие X>Y, Пролог-система не будет рассматривать альтернативное второе предложение. Второе предложение "сработает" только в случае, если условие оказалось ложным. В этой ситуации в третий аргумент попадет то же значение, которое находилось во втором аргументе. Обратите внимание, что в этом случае нам уже не важно, чему равнялся первый аргумент, и его можно заменить анонимной переменной.
Все случаи применения отсечения принято разделять на "зеленые" и "красные". Зелеными называются те из них, при отбрасывании которых программа продолжает выдавать те же решения, что и при наличии отсечения. Если же при устранении отсечений программа начинает выдавать неправильные решения, то такие отсечения называются красными.
Пример "красного" отсечения имеется в реализации предиката max2 (если убрать отсечение, предикат будет выдавать в качестве максимума второе число, даже если оно меньше первого). Пример "зеленого" отсечения можно получить, если в запись предиката max добавить отсечения (при их наличии предикат будет выдавать те же решения, что и без них).
В принципе, с помощью отсечения в Прологе можно смоделировать такую конструкцию императивных языков, как ветвление.
Процедура
S:-
<условие>,!,P.
S :-
P2.
будет соответствовать оператору if <условие> then P else P2, то есть если условие имеет место, то выполнить P, иначе выполнить P2. Например, в случае с максимумом, можно расшифровать нашу процедуру как "если X>Y, то M=X, иначе M=Y ".
Пример. Теперь напишем предикат, который будет находить максимум  не из двух чисел, а из трех. У него будет уже четыре параметра. Первые три - входные для сравниваемых чисел, а четвертый - выходной параметр для их максимума.
Подходов к решению этой задачи может быть несколько.
Первое, что приходит в голову, это решить задачу по аналогии с нахождением максимума из двух чисел. Вариант без отсечения будет выглядеть так:
max3a(X,Y,Z,X):-
X>=Y,X>=Z.
/* если первое число больше или равно второму
и третьему, то первое число - максимум */
max3a(X,Y,Z,Y):-
Y>=X,Y>=Z.
/* если второе число больше или равно первому
и третьему, то второе число является
максимумом */
max3a(X,Y,Z,Z):-
Z>=X,Z>=Y.
/* если третье число больше или равно первому
и второму, то максимум - это третье число */
Недостаток этой программы, кроме ее длины, еще и в том, что если какие-то из исходных чисел окажутся равными, мы получим несколько одинаковых решений. Например, если все три числа совпадают, то каждое из трех правил будет истинным и, соответственно, мы получим три одинаковых, хотя и правильных ответа.
Применение отсечения позволит существенно сократить решение:
max3b(X,Y,Z,X):-
X>Y,X>Z,!.
/* если первое число больше второго и третьего,
то первое число - максимум */
max3b(_,Y,Z,Y):-
Y>=Z,!.
/* иначе, если второе число больше третьего,
то второе число является максимумом */
max3b(_,_,Z,Z). /* иначе максимум - это третье число */
Число сравнений значительно сократилось за счет того, что отсечение в первом правиле гарантирует нам, что на второе правило мы попадем только в том случае, если первое число не больше второго и третьего. В этой ситуации максимум следует искать среди второго и третьего чисел. Если ни первое, ни второе число не оказались больше третьего, значит, в качестве максимума можно взять как раз третье число, уже ничего не проверяя. Обратите внимание на то, что во втором правиле нам было не важно, чему равно первое число, а в третьем предложении участвовало только третье число. Не участвующие параметры заменены анонимными переменными.
И, наконец, самое короткое решение можно получить, если воспользоваться уже имеющимся предикатом max2. Решение будет состоять всего из одного предложения.
max3(X,Y,Z,M):-
max2(X,Y,XY), /* XY - максимум из X и Y */
max2(XY,Z,M). /* M - максимум из XY и Z */
Мы записали, что для того, чтобы найти максимум из трех чисел, нужно найти максимум из первых двух чисел, после чего сравнить его с третьим числом.
В отличие от традиционных языков программирования, в которых основным средством организации повторяющихся действий являются циклы, в Прологе для этого используются процедура поиска с возвратом (откат) и рекурсия. Откат дает возможность получить много решений в одном вопросе к программе, а рекурсия позволяет использовать в процессе определения предиката его самого. При изучении рекурсии частенько вспоминается случай с бароном Мюнхгаузеном, который сам себя за волосы вытаскивал из болота. Про откат мы подробнее поговорим в шестой лекции, а в этой займемся изучением рекурсии. Заметим, что рекурсию  используют не только в Прологе, но и в обычных императивных языках программирования. Но для Пролога, в отличие от императивных языков, рекурсия является основным приемом программирования. Более того, Пролог позволяет определять рекурсивные структуры данных. Работе с ними будет посвящено несколько лекций нашего курса.
Начнем изучение рекурсии в Прологе с классического примера. Предположим, что в базе знаний есть набор фактов, описывающий родственные связи людей через отношение "быть родителем". Предикат родитель имеет два аргумента. В качестве его первого аргумента указывается имя родителя, в качестве второго - имя ребенка. Мы хотим создать отношение "быть предком", используя предикат  родитель.
Для того чтобы один человек был предком другого человека, нужно, чтобы он либо был его родителем, либо являлся родителем другого его предка.
Запишем эту идею:
предок(Предок,Потомок):-
родитель(Предок,Потомок).
/* предком является родитель */
предок(Предок,Потомок):-
родитель(Предок,Человек),
предок(Человек,Потомок).
/* предком является родитель предка */
Отношение предок является транзитивным замыканием отношения родитель, то есть это наименьшее отношение, включающее отношение родитель и обладающее свойством транзитивности. Напомним, что отношение называется транзитивным, если для любых пар (А,В) и (В,С), находящихся в этом отношении, пара (А,С) также находится в этом отношении. Очевидно, что отношение  предок содержит отношение  родитель. Это следует из первого предложения, в котором записано, что всякий родитель является предком. Второе предложение дает транзитивность.
По аналогии с математической индукцией, на которую рекурсия немного похожа, любая рекурсивная процедура должна включать в себя базис и шаг рекурсии.
Базис рекурсии - это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу даже без использования рекурсии. Так, в приведенной выше процедуре, описывающей предикат предок, базисом рекурсии является первое правило, в котором определено, что ближайшими предками человека являются его родители. Это предложение часто содержит условие, при выполнении которого происходит выход из рекурсии или отсечение.
Шаг рекурсии - это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката. Если мы хотим избежать зацикливания, определяемый предикат должен вызываться не от тех же параметров, которые указаны в заголовке правила. Параметры должны изменяться на каждом шаге так, чтобы в итоге либо сработал базис рекурсии, либо условие выхода из рекурсии, размещенное в самом правиле. В общем виде правило, реализующее шаг рекурсии, будет выглядеть так:
<имя определяемого предиката>:-
[<подцели>],
[<условие выхода из рекурсии>],
[<подцели>],
<имя определяемого предиката>,
[<подцели>].
В некоторых ситуациях предложений, реализующих базис рекурсии, и предложений, описывающих шаг рекурсии, может быть несколько. Как правило, это бывает в сложных случаях, например, когда выполняемые в процессе реализации шага рекурсиидействия зависят от выполнения или невыполнения какого-либо условия. Такие задачи встретятся нам в последующих лекциях, когда речь пойдет об обработке рекурсивных структур данных. В этой же лекции мы будем иметь дело в основном с простыми случаями рекурсии, когда рекурсивная процедура имеет один базис и один шаг рекурсии.
Пример. Создадим предикат, который будет вычислять по натуральному числу его факториал. Эта задача допускает рекурсивное решение на многих языках программирования, а также имеет рекурсивное математическое описание:
1!=1 /* факториал единицы равен единице */
N!=(N-1)!*N /* для того, чтобы вычислить факториал
некоторого числа, нужно вычислить
факториал числа на единицу меньшего
и умножить его на исходное число */
Попробуем записать реализацию предиката, эквивалентную математическому определению предиката:
fact(1,1). /* факториал единицы равен единице */
fact(N,F):-
N1=N-1,
fact(N1,F1), /* F1 равен факториалу числа
на единицу меньшего исходного
числа */
F=F1*N. /* факториал исходного числа равен
произведению F1 на само число */
К сожалению, при попытке вычислить факториал произвольного натурального числа с помощью описанного выше предикатаfact произойдет переполнение стека ( "Stack overflow" ). Попробуем разобраться, в чем причина. Рассмотрим, например, что будет происходить, если мы попытаемся вычислить факториал трех.
Соответствующий вопрос можно записать следующим образом:
fact(3,X).
Пролог-система попытается унифицировать цель с заголовком первого предложения ( fact(1,1) ). Ей это не удастся, поскольку число три не равно единице. При унификации цели с заголовком второго предложения ( fact(N,F) ) переменная Nконкретизируется числом три, а переменная X связывается с переменной F. После этого происходит попытка выполнить подцели, расположенные в теле правила слева направо. Сначала переменная N1 означивается числом на единицу меньшим, чемзначение переменной N, то есть двойкой. Срабатывание следующей подцели ( fact(N1,F1) ) приводит к рекурсивному вызову предиката, вычисляющего факториал, со значением переменной N1, равным двум.
Так же, как и в случае, когда первый аргумент был равен трем, унификации с головой первого предложения не происходит (единица не равна двум). Сопоставление с головой второго правила происходит успешно. Дальше все происходит почти так же, как для значения переменной N, равного трем. Вычисляется новое значение N1, равное двум без единицы, то есть единице.Пролог снова пытается вычислить подцель fact(N1,F1) (правда, со значением переменной N1, равным единице).
На этот раз происходит сопоставление цели ( fact(1,F1) ) с заголовком первого предложения, при этом переменная F1конкретизируется единицей. Пролог-системе наконец-то удалось вычислить вторую подцель второго правила, и она переходит к вычислению третьей подцели ( F=F1*N ). Переменная N была равна двум, переменная F1 - единице, произведение двух и единицы равно двум и, значит, переменная F конкретизируется двойкой.
Начинается обратный ход рекурсии. После того, как был вычислен факториал двойки, Пролог-система готова вычислитьфакториал тройки. Для этого нужно умножить факториал двух на три. Переменная F будет конкретизирована числом шесть. Мы получили ответ на вопрос о факториале трех.
Однако вычисления на этом не заканчиваются. Пролог-система обнаруживает, что цель fact(1,F1) может быть сопоставлена не только с заголовком первого предложения, но и с заголовком правила ( fact(N,F) ). Переменная N конкретизируется единицей, а переменная F1 связывается с переменной F. После этого переменная N1 означивается числом на единицу меньшим, чем значение переменной N, то есть нулем. Пролог-система пытается вычислить цель fact(0,F1). С заголовком первого предложения ( fact(1,1) ) сопоставить эту цель не удается, поскольку ноль не равен единице. Зато с заголовком второго предложения ( fact(N,F) ) цель успешно унифицируется. Переменная N1 становится равна минус единице. После этого делается попытка вычислить цель fact(-1,F1).... Потом fact(-2,F1), fact(-3,F1), fact(-4,F1),fact(-5,F1)... .
Этот процесс будет продолжаться до тех пор, пока не будет исчерпана часть оперативной памяти, отведенная под стек. После этого выполнение программы остановится с сообщением о том, что стек переполнен.
Почему так получилось? Что мы сделали неправильно? Причина в том, что в исходном определении факториала, которое мы использовали, предполагалось, что правило работает только для натуральных чисел, то есть для положительных целых чисел. У нас же в программе произошел выход в отрицательную часть целых чисел, что не было предусмотрено формулой, на которой была основана наша процедура.
Как можно исправить ошибку? У нас есть два варианта корректировки процедуры.
Можно проверить, что число, для которого применяется правило, больше единицы. Для единицы останется факт, утверждающий, что факториалом единицы будет единица. Выглядеть этот вариант будет следующим образом:
fact(1,1). /* факториал единицы равен единице */
fact(N,F):-
N>1, /* убедимся, что число больше единицы */
N1=N-1,
fact(N1,F1), /* F1 равен факториалу числа,
на единицу меньшего исходного
числа */
F=F1*N. /* факториал исходного числа равен
произведению F1 на само число */
В этом случае, хотя и произойдет повторное согласование цели fact(1,F1) с заголовком правила, и переменная N будет конкретизирована единицей, а переменная F связана с переменной F1, первая подцель правила ( N>1 ) будет ложной. На этом процесс оборвется. Попытки вычислять факториал на неположительных числах не произойдет, процедура будет работать именно так, как нам хотелось.
Второй вариант решения проблемы - добавить в первое предложение процедуры отсечение. Напомним, что вызов отсечения приводит к тому, что предложения процедуры, расположенные ниже той, из которой оно было вызвано, не рассматриваются. И, соответственно, после того, как какая-то цель будет согласована с заголовком первого предложения, сработает отсечение, и попытка унифицировать цель с заголовком второго предложения не будет предпринята. Процедура в этом случае будет выглядеть так:
fact(1,1):-!. /* условие останова рекурсии */
fact(N,F):-
N1=N-1,
fact(N1,F1), /* F1 равен факториалу числа,
на единицу меньшего исходного
числа */
F=F1*N. /* факториал исходного числа равен
произведению F1 на само число */
Конечно, с одной стороны, метод рекурсии имеет свои преимущества перед методом итерации, который используется в императивных языках программирования намного чаще. Рекурсивные алгоритмы, как правило, намного проще с логической точки зрения, чем итерационные. Некоторые алгоритмы удобно записывать именно рекурсивно.
С другой стороны, рекурсия имеет большой недостаток: ей, вообще говоря, может не хватать для работы стека. При каждом рекурсивном вызове предиката в специальном стековом фрейме запоминаются все промежуточные переменные, которые могут понадобиться. Максимальный размер стека при работе под управлением операционной системы MS DOS всего 64 Кб. Этого достаточно для размещения около трех-четырех тысяч стековых фреймов (в зависимости от количества и размера промежуточных переменных). При больших входных значениях стека может не хватить.
Есть, правда, один вариант рекурсии, который использует практически столько же оперативной памяти, сколько итерация в императивных языках программирования. Это так называемая хвостовая или правая рекурсия. Для ее осуществления рекурсивный вызов определяемого предиката должен быть последней подцелью в теле рекурсивного правила и к моменту рекурсивного вызова не должно остаться точек возврата (непроверенных альтернатив). То есть у подцелей, расположенных левее рекурсивного вызова определяемого предиката, не должно оставаться каких-то непроверенных вариантов и у процедуры не должно быть предложений, расположенных ниже рекурсивного правила. Турбо Пролог, на который мы ориентируемся в нашем курсе, распознает хвостовую рекурсию и устраняет связанные с ней дополнительные расходы. Этот процесс называется оптимизацией хвостовой рекурсии или оптимизацией последнего вызова.
Пример. Попробуем реализовать вычисление факториала с использованием хвостовой рекурсии. Для этого понадобится добавить два дополнительных параметра, которые будут использоваться нами для хранения промежуточных результатов. Третий параметрнужен для хранения текущего натурального числа, для которого вычисляется факториал, четвертый параметр - для факториала числа, хранящегося в третьем параметре.
Запускать вычисление факториала мы будем при первом параметре равном числу, для которого нужно вычислить факториал. Третий и четвертый аргументы будут равны единице. Во второй аргумент по завершении рекурсивных вычислений должен быть помещен факториал числа, находящегося в первом параметре. На каждом шаге будем увеличивать третий аргумент на единицу, а второй аргумент умножать на новое значение третьего аргумента. Рекурсию нужно будет остановить, когда третий аргументсравняется с первым, при этом в четвертом аргументе будет накоплен искомый факториал, который можно поместить в качестве ответа во второй аргумент.
Вся процедура будет выглядеть следующим образом:
fact2(N,F,N,F):-!. /* останавливаем рекурсию, когда третий
аргумент равен первому*/
fact2(N,F,N1,F1):-
N2=N1+1, /* N2 - следующее натуральное число
после числа N1 */
F2=F1*N2, /* F2 - факториал N2 */
fact2(N,F,N2,F2).
/* рекурсивный вызов с новым натуральным
числом N2 и соответствующим ему
посчитанным факториалом F2 */
Остановить рекурсию можно, воспользовавшись отсечением в базисе рекурсии, как это было сделано выше, или добавив в начало второго предложения сравнение N1 с N.
Если мы решим, что вызывать предикат с четырьмя аргументами неудобно, можно ввести дополнительный двухаргументныйпредикат, который будет запускать исходный предикат:
factM(N,F):-
fact2(N,F,1,1). /* вызываем предикат с уже
заданными начальными
значениями */
Пример. В предыдущей лекции мы записали аналог императивного ветвления, воспользовавшись отсечением. Теперь напишем, используя рекурсию и отсечение, реализацию цикла с предусловием. Обычно этот цикл выглядит примерно так: while <условие> do P. Это соответствует текстовому описанию "пока имеет место <условие>, выполнять P ". На Прологе подобную конструкцию можно записать следующим образом:
w:-
<условие>,p,w.
w:-!.
Пример. Еще одна классическая задача, имеющая рекурсивное решение, связана с вычислением так называемых чисел Фибоначчи. Числа Фибоначчи можно определить так: первое и второе числа равны единице, а каждое последующее число является суммой двух предыдущих. Соответственно, третье число Фибоначчи будет равно двум, четвертое равно трем (сумма второго числа (один) и третьего числа (два)), пятое - пяти (сумма третьего и четвертого чисел, то есть двух и трех), шестое - восьми (сумма четвертого и пятого, трех и пяти) и т.д.
Базисов рекурсии в данном случае два. Первый будет утверждать, что первое число Фибоначчи равно единице. Второй базис - аналогичное утверждение про второе число Фибоначчи. Шаг рекурсии также будет необычным, поскольку будет опираться при вычислении следующего числа Фибоначчи не только на предшествующее ему число, но и на предшествующее предыдущему числу. В нем будет сформулировано, что для вычисления числа Фибоначчи с номером N сначала нужно вычислить и сложить числа Фибоначчи с номерами N-1 и N-2.
Записать эти рассуждения можно так:
fib(1,1):-!. /* первое число Фибоначчи равно единице */
fib(2,1):-!. /* второе число Фибоначчи равно единице */
fib(N,F) :-
N1=N-1, fib(N1,F1), /* F1 это N-1-е число
Фибоначчи */
N2=N-2, fib(N2,F2), /* F2 это N-2-е число
Фибоначчи */
F=F1+F2. /* N-е число Фибоначчи равно сумме
N-1-го и N-2-го чисел Фибоначчи */
Обратите внимание на отсечение в первых двух предложениях. Оно служит для остановки рекурсии, чтобы при прямом ходерекурсии не произошло выхода из области натуральных чисел (номеров чисел Фибоначчи) в область отрицательных чисел, как это происходило у нас в первой версии предиката, вычисляющего факториал.
Вместо этих двух отсечений от зацикливания можно избавиться путем добавления в начало правила, реализующего шаг рекурсии, проверки значения, находящегося в первом параметре предиката ( N>2 ). Это условие в явном виде указывает, что рекурсивное правило применяется для вычисления чисел Фибоначчи, начиная с третьего.
Но надо сказать, что хотя наше решение получилось ясным и прозрачным, довольно точно соответствующим определению чисел Фибоначчи, оно, тем не менее, весьма неэффективное. При вычислении N-1 -го числа Фибоначчи F1 вычисляются все предыдущие числа Фибоначчи, в частности, N-2 -е число Фибоначчи F2. После этого заново начинает вычисляться N-2 -е число Фибоначчи, которое уже было вычислено. Мало того, опять вычисляются все предыдущие числа Фибоначчи. Получается, что для вычисления числа Фибоначчи используется количество рекурсивных вызовов предиката fib, равное искомому числу Фиббоначи.
Давайте попробуем повысить эффективность вычисления чисел Фибоначчи. Будем искать сразу два числа Фибоначчи: то, которое нам нужно найти, и следующее за ним. Соответственно, предикат будет иметь третий дополнительный аргумент, в который и будет помещено следующее число. Базис рекурсии из двух предложений сожмется в одно, утверждающее, что первые два числа Фибоначчи равны единице.
Вот как будет выглядеть этот предикат:
fib_fast(1,1,1):-!. /* первые два числа Фибоначчи равны
единице */
fib_fast(N,FN,FN1):-
N1=N-1,fib_fast(N1,FN_1,FN),
/* FN_1 это N-1-е число
Фибоначчи, FN это
N-е число Фибоначчи */
FN1=FN+FN_1. /* FN1 это N+1-е число Фибоначчи */
Несмотря на то, что предикат fib_fast находит, в отличие от предиката fib, не одно число Фибоначчи, а сразу два, он использует намного меньше стекового пространства и работает во много раз быстрее. Для вычисления числа Фибоначчи с номером N (а заодно и N+1 -го числа Фибоначчи) необходимо всего лишь N рекурсивных вызовов предиката fib_fast.
Если нам не нужно следующее число Фибоначчи, можно сделать последним аргументом анонимную переменную или добавить описанный ниже двухаргументный предикат:
fib_fast(N,FN):-
fib_fast(N,FN,_).
Обратите внимание, что если во втором правиле процедуры, описывающей предикат предок, с которого мы начали знакомство срекурсией, изменить порядок подцелей, с декларативной точки зрения смысл останется прежним:
предок2(Предок,Потомок):-
родитель(Предок,Потомок). /* предком является
родитель */
предок2(Предок,Потомок):-
предок2(Человек,Потомок), /* предком является
родитель предка */
родитель(Предок,Человек).
Однако работать модифицированная процедура будет совсем не так. В случае, если вызвать предикат предок2, указав в качестве аргументов имена людей, один из которых является предком другого, он успешно подтвердит, что первый человек - предок второго. Во всех остальных ситуациях (один из аргументов свободен; человек, имя которого указано в качестве первого аргумента, не является предком человека, чье имя указано в качестве второго аргумента) все произойдет не так, как следовало бы. После того, как этот предикат выдаст те же ответы, что и исходный предикат предок, он зациклится и в итоге выдаст сообщение о том, что стек переполнен.
С оригинальным предикатом предок этого не происходило, потому что в его втором правиле первой подцелью стоял вызов подцели родитель. В результате выполнения этой подцели переменная Человек получала в качестве значения имя какого-то человека. Поэтому в момент вызова второй подцели предок(Человек,Потомок) переменная Человек была уже связанной. В новой же версии предиката второе правило начинается с вызова подцели предок2(Человек,Потомок), причем переменнаяЧеловек в ней свободна. После того, как будут исчерпаны все альтернативы для означивания свободных переменных через первое предложение процедуры, подцель будет унифицироваться с заголовком второго предложения. Свободная переменнаяЧеловек будет связана с переменной Предок, а переменная Потомок подцели - с переменной Потомок заголовка правила. При попытке выполнить первую подцель правила все повторится. Этот процесс будет продолжаться до тех пор, пока не будет исчерпано все свободное пространство стека.
Такой вид рекурсии, когда тело правила начинается с рекурсивного вызова определяемого предиката, называется левосторонней рекурсией. С левосторонней рекурсией очень часто возникают описанные проблемы. Поэтому нужно стараться, если возможно, избегать использования левосторонней рекурсии, в отличие от правосторонней или хвостовой рекурсии.
15

Приложенные файлы

  • doc 18049065
    Размер файла: 101 kB Загрузок: 0

Добавить комментарий