Problem with recursive predicate on Prolog

Question

Goal a(3, X) should return 6. Based on this code. I have converted it to Prolog code but with a problem in a recursive predicate. First two lines are for 0 and 1 to return the same value.

c=1
  for i = 2 to n do
    if c > i then
      c=c-1
    else
      c=c+1
    end if
end for
return c

But at Step 4 it gets the result and then goes back to step 2 and goes back with the iteration to the wrong result. I think there is a unification problem but can't find where.

a(N, N) :- N < 2, !.
a(N, X) :- a(1, 2, N, X).

Step 2.

a(C1, I, N, C1) :- I > N, !.

Step 3.

a(C, I, N, C1) :- C > I, !,
                 C1 is C - I,
                 I1 is I + 1,
                 a(C1, I1, N, C1).

Step 4.

a(C, I, N, C1) :- C =< I, !,
                 C1 is C + I,
                 I1 is I + 1,
                 a(C1, I1, N, C1).

This is the trace.

[trace]  ?- a(3, X).
   Call: (8) a(3, _1238) ? creep
   Call: (9) 3<2 ? creep
   Fail: (9) 3<2 ? creep
   Redo: (8) a(3, _1238) ? creep
   Call: (9) a(1, 2, 3, _1238) ? creep
   Call: (10) 2>3 ? creep
   Fail: (10) 2>3 ? creep
   Redo: (9) a(1, 2, 3, _1238) ? creep
   Call: (10) 1>2 ? creep
   Fail: (10) 1>2 ? creep
   Redo: (9) a(1, 2, 3, _1238) ? creep
   Call: (10) 1=<2 ? creep
   Exit: (10) 1=<2 ? creep
   Call: (10) _1474 is 1+2 ? creep
   Exit: (10) 3 is 1+2 ? creep
   Call: (10) _1480 is 2+1 ? creep
   Exit: (10) 3 is 2+1 ? creep
   Call: (10) a(3, 3, 3, 3) ? creep
   Call: (11) 3>3 ? creep
   Fail: (11) 3>3 ? creep
   Redo: (10) a(3, 3, 3, 3) ? creep
   Call: (11) 3>3 ? creep
   Fail: (11) 3>3 ? creep
   Redo: (10) a(3, 3, 3, 3) ? creep
   Call: (11) 3=<3 ? creep
   Exit: (11) 3=<3 ? creep
   Call: (11) _1486 is 3+3 ? creep
   Exit: (11) 6 is 3+3 ? creep
   Call: (11) _1492 is 3+1 ? creep
   Exit: (11) 4 is 3+1 ? creep
   Call: (11) a(6, 4, 3, 6) ? creep
   Call: (12) 4>3 ? creep
   Exit: (12) 4>3 ? creep
   Exit: (11) a(6, 4, 3, 6) ? creep  !!! SHOULD STOP HERE !!!
   Exit: (10) a(3, 3, 3, 3) ? creep
   Exit: (9) a(1, 2, 3, 1) ? creep
   Exit: (8) a(3, 1) ? creep
X = 1 .

These are other return values: 0 -> 0, 1 -> 1, 2 -> 3, 3 -> 6, 4 -> 2 — Ishmael Black
I think your pseudo-code is incorrect and doesn't provide the results you say you want. It certainly doesn't match your Prolog code. Your Prolog code would indicate that your pseudo code c=c-1 should be c=c-i and c=c+1 should be c=c+i. — lurker

lurker lurker · Accepted Answer · 2018-12-10T02:22:48

You need another variable. You're "overloading" C1, so it's already instantiated (bound) when you are doing your recursive call and you end up with things like this in the trace (note, using the code you show, I don't get the same trace you do, so you've done something different with your code):

| ?- a(3,X).
      1    1  Call: a(3,_23) ?
      2    2  Call: 3<2 ?
      2    2  Fail: 3<2 ?
      2    2  Call: a(1,2,3,_23) ?
      3    3  Call: 2>3 ?
      3    3  Fail: 2>3 ?
      3    3  Call: 1>2 ?
      3    3  Fail: 1>2 ?
      3    3  Call: 1=<2 ?
      3    3  Exit: 1=<2 ?
      4    3  Call: _23 is 1+2 ?
      4    3  Exit: 3 is 1+2 ?
      5    3  Call: _174 is 2+1 ?
      5    3  Exit: 3 is 2+1 ?
      6    3  Call: a(3,3,3,3) ?
      7    4  Call: 3>3 ?
      7    4  Fail: 3>3 ?
      7    4  Call: 3>3 ?
      7    4  Fail: 3>3 ?
      7    4  Call: 3=<3 ?
      7    4  Exit: 3=<3 ?
      8    4  Call: 3 is 3+3 ?
      8    4  Fail: 3 is 3+3 ?  <--- FAILS HERE: DUE TO C1 ALREADY BOUND
                                     3 cannot be 3+3 !
      6    3  Fail: a(3,3,3,3) ?
      2    2  Fail: a(1,2,3,_23) ?
      1    1  Fail: a(3,_23) ?

(1 ms) no

So here's the correction with an additional variable:

a(C, I, N, C1) :- C > I, !,
                 C2 is C - I,
                 I1 is I + 1,
                 a(C2, I1, N, C1).

a(C, I, N, C1) :- C =< I, !,
                 C2 is C + I,
                 I1 is I + 1,
                 a(C2, I1, N, C1).

Then you get:

| ?- a(3,X).

X = 6

(1 ms) yes
| ?-

As an aside, don't be so quick to sprinkle cuts throughout your code. Get it all working first without them. Then put them in very intentionally to prune decision branches. They sometimes prune out paths that you really want and lead to undesirable results.

Problem with recursive predicate on Prolog

1 Answers