Recursion on Prolog

Question

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?

Answer 1

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.

Answer 2

As recommended by @false, the best approach is to use library(clpfd). However, if you don't want to use that library, a possible solution is to consider two different cases:

• deterministic case [natural N to be converted into Peano's form is a constant]: starting from N, recursively decrement this value, until reach value 0 (a unique solution can be generated).

• non-deterministic case [natural N to be converted into Peano's form is a variable]: starting from 0, recursivelly increment this value, producing a new natural N at each step (infinitely many solutions can be generated).

% nat(?Natural, ?Peano)

  nat(N, P) :-
     (  integer(N) -> nat_det(N, P)
     ;  var(N)     -> nat_nondet(N, P)).

  nat_det(0, 0) :- !.
  nat_det(N, s(P)) :-
     succ(M, N),
     nat_det(M, P).

  nat_nondet(0, 0).
  nat_nondet(N, s(P)) :-
     nat_nondet(M, P),
     succ(M, N).

Here are some examples:

?- nat(2, P).
P = s(s(0)).

?- nat(2, s(s(0))).
true.

?- nat(2, s(s(s(0)))).
false.

?- nat(N, s(s(s(0)))).
N = 3.

?- N = 4, nat(N, P).
N = 4,
P = s(s(s(s(0)))).

?- nat(N, P), N = 4, !. % we know that there exist only one solution!
N = 4,
P = s(s(s(s(0)))).

?- nat(N, P).
N = P, P = 0 ;
N = 1,
P = s(0) ;
N = 2,
P = s(s(0)) ;
N = 3,
P = s(s(s(0))) ;
...