I'm trying to approach a problem in which given M and N integers, returns in res a list with the powers of M that are less than or equal to N, in descending order. example: powers(3,9,res). res = [9,3,1]

My approach is as follows:

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).

I'm getting my memory stack filled so I understand that the recursion never ends.

CodePudding user response：

You need to handle special cases:

• 0ⁿ is always 0
• 1ⁿ is always 1

And Prolog has an in-built exponiation function: **/2.

A common Prolog idiom is to have a public predicate that does little outside of constraint validation, that invokes an "internal" helper predicate that does the work. The helper predicate often takes additional parameters that maintain state needed for computation.

That leads to this:

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!    

Which gives us

?- powers(2,1024,Ps).

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