Основы современных компьютерных технологий


Рекурсивные вычисления - часть 2


/p>

На первом шаге выполняется целевой запрос fact(3,Res) и выбирается первый вариант решения: правило fact( 1,1):-!, сопоставление для него заканчивается неуспехом, так как 3#1, происходит откат и выбирается второе правило. Для него сопоставление с заголовком правила заканчивается успешно, при этом выполняется подстановка N=3, Res=R, тело правила помещается в стек и начинают отрабатываться предикаты тела. Первый из них - сравнение Next_N=N-1, оно завершается успешно, переменная Next_N становится равной 2.

Затем инициируется вызов fact(2,P), снова выбирается первый вариант правила, сопоставление 1 #2 приводит к неуспеху, происходит откат и выбор второго варианта правила. Здесь сопоставление с заголовком правила заканчивается успешно, при этом выполняется подстановка N'=2, P'=R', новая копия правила помещается в стек и начинается его выполнение. Первое из них - сравнение Next_N'=N'-1 - завершается успешно, копия переменной Next_N' становится равной 2-1 =1.

Затем выполняется вызов fact(1,P'). Снова производится сопоставление с первым вариантом, и вот здесь оно становится успешным, подстановка имеет вид 1=1, Р'=1, тело первого правила пусто, поэтому никаких действий не инициирует и начинается выполнение "хвостов", оставшихся в стеке от копий второго правила, в результате этих вычислений переменная Res получит значение, равное 6, которое и будет выведено на экран следующим предикатом запроса write("Факториал 3= ", Res). Отметим, что в первом утверждении применено отсечение !. Сделано это для того, чтобы в случае использования внешнего запроса вида fасt(1 ,Res), т.е. запроса на вычисление факториала 1, после успешного сопоставления запроса с первым утверждением (1 = 1,Res=1) отсечь второй вариант правила для нахождения альтернативного решения. Если этого не сделать, то второе правило приведет к зацикливанию и ошибке. Для обеспечения корректной работы программы для запроса fact(0, Res) в раздел clauses нужно добавить еще одно утверждение, а именно fact(0,1):-!.

318

317 :: 318 :: Содержание




Начало  Назад  Вперед