tail recursion sum, power, gcd in prolog?

Question

hi guys, how can I accomplish this:

Give a tail-recursive definition for each of the following predicates. power(X,Y,Z): XY=Z. gcd(X,Y,Z): The greatest common divisor of X and Y is Z. sum(L,Sum): Sum is the sum of the elements in L.

so far I have done this but not sure if that's correct

power(_,0,1) :- !.
power(X,Y,Z) :- Y1 is Y - 1,power(X,Y1,Z1),Z is X * Z1.

sum(void,0). sum(t(V,L,R),S) :- sum(L,S1),sum(R,S2), S is V + S1 + S2.

please help. my email is [email protected]

Answer 1

These are not tail recursive. You can write tail recursive variants by using an accumulator, see this answer.

Your sum is over a tree, which is unusual, normally one would use a list. In Prolog [] is the empty list and [X|R] is the pattern for a nonempty list with the head X and the tail R.

Answer 2

anybody else can help me but starblue? I like to learn at the begining by seeing examples... not an easy language to handle.

Answer 3

I found some code here: http://fmi.spiruharet.ro/bodorin/aicl.html Claudio