math - 序言中的幂函数

Question

我的幂函数有什么问题？

pow(_,0,1).   
pow(X,Y,Z) :-
    pow(X,Y-1,X*Z).

?- pow(2,3,Z).
ERROR: Out of global stack

Answer 1

您的 Y 不会递减，您不能使用函数之类的谓词。您还必须将 Z 与乘法的结果统一起来。

pow(_,0,1).

pow(X,Y,Z) :- Y1 is Y - 1,
              pow(X,Y1,Z1), Z is Z1*X.

还有一个内置的幂函数会更快:

pow2(X,Y,Z) :- Z is X**Y.

另请注意， pow 不是最后一次调用，无法优化为仅使用一个堆栈帧。您应该将其重新表述为:

pow3(X,Y,Z) :- powend(X,Y,1,Z),!.

powend(_,0,A,Z) :- Z is A.
powend(X,Y,A,Z) :- Y1 is Y - 1, A1 is A*X, powend(X,Y1,A1,Z).