是什么导致无限递归？（序言）

Question

我正在尝试解决一个问题，其中给定 M 和 N 个整数，returns 在 res 列表中，M 的幂小于或等于 N，按降序排列。示例：权力（3,9，资源）。 res = [9,3,1]

我的做法如下：

power(X,0,1).
power(X,Y,Z) :- X>0,
           Yminus1 is Y - 1,
           power(X,Yminus1,Z1), 
           Z is X*Z1.

increment(X,newX) :- newX is X + 1.

powers(M,N,res) :- integer(M), integer(N),
    powersAux(M,N,0,res).

powersAux(M,N,E,res) :- power(M,E,Z),
                    Z=<N,
                    increment(E,E1),
                    res1 = [Z|res],
                    powersAux(M,N,E1,res1).

我正在填满我的内存堆栈，所以我知道递归永远不会结束。

Answer 1

您需要处理特殊情况：

0ⁿ 总是 0
1ⁿ 总是 1

并且 Prolog 有一个 in-built 求幂函数：**/2。

一个常见的 Prolog 习惯用法是有一个 public 谓词，它在约束验证之外几乎不做任何事情，它调用一个“内部”辅助谓词来完成这项工作。辅助谓词通常采用额外的参数来维护计算所需的状态。

这导致：

powers( X , L, Ps ) :-
    non_negative_integer(X),
    non_negative_integer(L),
    powers(X,0,L,[],Ps)
    .

non_negative_integer(X) :- integer(X), X >= 0 .

% ---------------------------------------------------------------
% 
% powers( +Base, +Exponent, +Limit, +Accumulator, ?Results )
% 
% where Base and Radix are guaranteed to be non-negative integers
% ---------------------------------------------------------------
powers( 0 , _ , _ , _  , [0] ) :- ! .            % 0^n is always 0
powers( 1 , _ , 0 , _  , []  ) :- ! .            % 1^n is always 1
powers( 1 , _ , L , _  , [1] ) :- L >= 1 , !.    % 1^n is always 1
powers( X , Y , L , Ps , Ps  ) :- X**Y >  L , !. % when x^y exceeds the limit, we're done, and
powers( X , Y , L , Ts , Ps  ) :-                % otherrwise...
    T is X**Y ,                                  % - compute T as x^y
    Y1 is Y+1,                                   % - increment Y
    powers(X,Y1,L,[T|Ts],Ps)                     % - recurse down, prepending T to the accumulator list.
    .                                            % Easy!

这给了我们

?- powers(2,1024,Ps).

Ps = [1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]

是什么导致无限递归？（序言）

What is causing an infinite recursion? (Prolog)

recursion

prolog

是什么导致无限递归？ （序言）

What is causing an infinite recursion? (Prolog)

recursion

prolog

是什么导致无限递归？（序言）