Мне действительно трудно понять, как работает рекурсия в Прологе.
factorial(0,1).
factorial(N,F) :-
N>0,
N1 is N-1,
factorial(N1,F1),
F is N * F1.
Я так понимаю первая часть это базовый вариант и на этом продолжение программы закончится. Однако меня смущают параметры второго факторного вызова (N1, F1). Может ли кто-нибудь объяснить шаги, как все выполняется и рассчитывается?
Второе правило в основном говорит, что F является факториалом N если N больше нуля и существует число N1, которое является результатом N-1 и strong> F1 — это факториал N1 и F — произведение N и F1.
Пример
Допустим, вы хотите найти факториал числа 3.
-? factorial(3,F).
Пролог помещает factorial(3,F) в стек целей, а затем ищет правила, голова которых соответствует первой цели. Для factorial/2 есть два правила (факт factorial(0,1) можно увидеть как правило без тела), но для первого 0 не унифицируется с 5, поэтому его нельзя использовать. Второй объединяется с N, инстанцируемым до 5, и Пролог добавляет условия в стек, который становится:
3 > 0, N1 is 3-1, factorial(N1,F1), F is 3*F1
Первая цель достигнута, так как 3 больше нуля. Второй удовлетворяется привязкой N1 к результату арифметического вычисления 3-1, так что стек целей теперь такой:
factorial(2,F1), F is 3*F1
Опять же, Пролог ищет правила, которые могут быть использованы для удовлетворения factorial(2,F1), и использует второе (N объединяется с 2 и F с F1, а для переменных используются разные имена):
2 > 0, N2 is 2-1, factorial(N2,F2), F1 is 2*F2, F is 3*F1
Далее, 2 > 0 истинно, а N2 объединяется с арифметическим результатом 2-1, поэтому стек целей становится следующим:
factorial(1,F2), F1 is 2*F2, F is 3*F1
Используя снова второе правило для factorial/2:
1 > 0, N3 is 1-1, factorial(N3,F3), F2 is 1*F3, F1 is 2*F2, F is 3*F1
N3 становится равным нулю (когда выполняется N3 is 1-1):
factorial(0,F3), F2 is 1 * F3, F1 is 2*F2, F is 3*F1
На этом этапе первое правило для factorial/2 может быть использовано для удовлетворения factorial(0, F3), но создается точка выбора, так как есть больше правил, которые можно использовать. Таким образом, factorial(0,F3) преуспевает, присваивая F3 значение 1.
F2 is 1 * 1, F1 is 2 * F2, F is 3 * F3
Удовлетворив все цели, оставшиеся в стеке, F станет 6, и вы получите свое первое решение. Но была точка выбора для factorial(0, F3). В этот момент можно использовать второе правило:
0>0, N4 is 0-1, factorial(N4,F4), F3 is 0*F4, F2 is 1*F3, F1 is 2*F2, F is 3*F3
Но 0>0 терпит неудачу, и выполнение останавливается, поскольку нет другого выбора, на который можно вернуться.
Вы можете не оставлять эту бесполезную точку выбора для factorial(0,_), используя [зеленый] оператор вырезания.
factorial(0, 1) :- !.
