Пролог факториальная рекурсия

Question

У меня проблемы с пониманием следующей факторной программы

fact1(0,Result) :-
    Result is 1.
fact1(N,Result) :-
    N > 0,
    N1 is N-1,
    fact1(N1,Result1),
    Result is Result1*N.

Когда fact1 называется вложенным во второй fact1, не означает ли это, что последняя строка, Result is Result1*N., никогда не вызывается? Или в Прологе последняя строка выполняется перед рекурсивным вызовом?

Answer 1

Кстати, как только вы поймете базовую рекурсию, попробуйте добиться хвостовой рекурсии, когда это возможно, вот это будет:

factorial(N, R) :- factorial(N, 1, R).
factorial(0, R, R) :- !.
factorial(N, Acc, R) :-
    NewN is N - 1,
    NewAcc is Acc * N,
    factorial(NewN, NewAcc, R).

Хвостовая рекурсия, в отличие от рекурсии, которую вы использовали ранее, позволяет интерпретатору / компилятору очищать контекст при переходе к следующему шагу рекурсии. Допустим, вы вычислили factorial(1000), ваша версия будет поддерживать 1000 контекстов, в то время как моя версия будет поддерживать только 1. Это означает, что ваша версия в конечном итоге не будет рассчитывать желаемый результат, а просто потерпит крах при ошибке Out of call stack memory.

Вы можете узнать больше об этом в Википедии.

Answer 2

Довольно простой способ сделать это так:

fac(0,1).
fac(N,F):-
    N>0,N1 is N-1,fac(N1,F1),F is N*F1.

Answer 3

Нет, рекурсивный вызов происходит первым!Должен, иначе последний пункт не имеет смысла.Алгоритм разбивается на:

factorial(0) => 1
factorial(n) => factorial(n-1) * n;

Как видите, вам нужно вычислить результат рекурсии перед умножением, чтобы получить правильное значение!

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

Answer 4

Вообще говоря, ответ @ m09 в основном прав насчет важности хвостовой рекурсии.

Для больших N, расчет продукта по-другому выигрывает! Подумайте «двоичное дерево», а не «линейный список» ...

Давайте попробуем оба способа и сравним время выполнения. Во-первых, @ m09's factorial/2:

?- time((factorial(100000,_),false)).
% 200,004 inferences, 1.606 CPU in <b>1.606</b> seconds (100% CPU, 124513 Lips)
false.

Далее мы делаем это в древовидном стиле - используя мета-предикат reduce/3 вместе с лямбда-выражениями :

?- time((numlist(1,100000,Xs),reduce(\X^Y^XY^(XY is X*Y),Xs,_),false)).
% 1,300,042 inferences, 0.264 CPU in <b>0.264</b> seconds (100% CPU, 4922402 Lips)
false.

Наконец, давайте определим и используем выделенный вспомогательный предикат x_y_product/3:

x_y_product(X, Y, XY) :- XY is X*Y.

Что выиграть? Давайте попросим секундомер !

?- time((numlist(1,100000,Xs),reduce(x_y_product,Xs,_),false)).
% 500,050 inferences, 0.094 CPU in <b>0.094</b> seconds (100% CPU, 5325635 Lips)
false.

Answer 5

Базовый случай объявлен.Условие, что N должно быть положительным и умножаться на предыдущий член.

 factorial(0, 1).
 factorial(N, F) :- 
       N > 0, 
       Prev is N -1, 
       factorial(Prev, R), 
       F is R * N.

Для выполнения:

факториал (-1, X).

Answer 6

factorial(1, 1).
factorial(N, Result) :- M is N - 1,
factorial(M, NextResult), Result is NextResult * N.

Answer 7

Простой способ:

 factorial(N, F):- N<2, F=1.

 factorial(N, F) :- 
     M is N-1, 
     factorial(M,T), 
     F is N*T.

Answer 8

рекурсия не-тейлера:

 fact(0,1):-!. 
   fact(X,Y):- Z=X-1,
         fact(Z,NZ),Y=NZ*X.

рекурсия тейлера:

fact(X,F):- X>=0,fact_aux(X,F,1).
fact_aux(0,F,F):-!.
   fact_aux(X,F,Acc):- 
       NAcc=Acc*X, NX=X-1, 
    fact_aux(NX,F,NAcc).

Answer 9

Я бы сделал что-то вроде:

fact(0, 1).
fact(N, Result):-
    Next is N - 1,
    fact(Next, Recursion),
    Result is N * Recursion.

И хвостовая версия будет выглядеть так:

tail_fact(0, 1, 0).         /* when trying to calc factorial of zero */
tail_fact(0, Acc, Res):-    /* Base case of recursion, when reaches zero return Acc */
     Res is Acc.
tail_fact(N, Acc, Res):-    /* calculated value so far always goes to Acc */
     NewAcc is N * Acc,
     NewN is N - 1,
     tail_fact(NewN, NewAcc, Res).

Так что вам позвонить:

нехвостовой рекурсивный метод: факт (3, результат).

метод хвостовой рекурсии: tail_fact (3, 1, Result).

Это может помочь;)