recursion - Prolog递归溢出

Question

fact(1,1):-!.
fact(N,F):-
    N1=N-1,
    fact(N1,F1),
    F=F1*N.

它导致stackoverflow（不是站点）！这不应该是因为cut（！）。它在 SWI-Prolog 中有效吗？

Answer 1

请注意，对于像fact(0,N). 但也fact(1,2)不会终止。它应该失败。因为fact(N, F)它只给出一个正确答案，但应该有无限多。为此目的使用削减是非常棘手的。解决这个问题的最干净的方法是将目标添加N > 0到规则中并有一个事实fact(0,1).如果您使用 SWI-Prolog，还有一个更好的方法：使用library(clpfd). 在文档中，您会发现n_factorial/2已经定义。它可用于以下查询：

?- n_factorial(47, F).
F = 258623241511168180642964355153611979969197632389120000000000 ;
false.

?- n_factorial(N, 1).
N = 0 ;
N = 1 ;
false.

?- n_factorial(N, 3).
false.