recursionprologsuccessor-arithmetics

Recursion on Prolog

I'm trying to write a Prolog recursion that will return the following representation for numbers:

1 --> s(0)

2 --> s(s(0))

3 --> s(s(s(0))) ...

I used the following code:

retnum(s(0),1). %Stop Condition
retnum(S,Z):-
    retnum(s(S),Z1),
    Z is Z1+1.

but when I try to run prediction :

retnum(A,2).

I get result A=0, and if I continue I get error with stuck limit exceeded. I was expecting to get a result A = s(s(0)). I tried also to add additional stop condition : retnum(0,0).

Any idea where is my mistake and if there is better way to do it?

Solution

  • You are using the recursive call incorrectly. The argument to the recursive instance should be smaller than the original (more generally: converging to a boundary condition). This might give you what you want:

    retnum(s(0), 1).
retnum(s(S), Z) :-
    retnum(S, Z1),
    Z is Z1 + 1.

    But this is even better.

    retnum1(s(0), 1).
retnum1(s(S), Z) :-
    Z > 1, Z1 is Z - 1,
    retnum1(S, Z1).

    Try to trace/0 and see why it is so.