Prolog阶乘递归

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.永远不会被调用？或者在Prolog中,最后一行是在递归调用之前执行的吗？

Answer 1

BTW一旦你理解了基本的递归,尽可能尝试实现尾递归,这里它是:

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;

如您所见,您需要在乘法之前计算递归的结果,以便返回正确的值!

您的prolog实现可能有一种方法来启用跟踪,这将让您看到整个算法运行.这可能会帮助你.

Answer 4

一般来说,@ m09的答案基本上是关于尾递归的重要性.

对于大 N,计算产品不同赢!想想"二叉树",而不是"线性列表"......

让我们尝试两种方式并比较运行时间.首先,@ m09factorial/2:

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

接下来,我们使用meta-predicate reduce/3和lambda表达式来树形式:

?- time((numlist(1,100000,Xs),reduce(\X^Y^XY^(XY is X*Y),Xs,_),false)).
% 1,300,042 inferences, 0.264 CPU in 0.264 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 0.094 seconds (100% CPU, 5325635 Lips)
false.