Prolog recursive subtraction

Question

I picked up prolog a couple of days ago and I 'm kind of stuck to this question. I want to subtract a number recursively until that number becomes less than 0. In pseudocode that would be like:

N:=0
while(Y>=X)
{
    Y := Y-X
    N := N+1
    Y := Y+2
}

So for example if I have Y=20 and X=10 then we would get N=2 and Y=4.

Any ideas? Thanks in advance. Any help appreciated. I'm using SWI Prolog.

EDIT 1 What I've accomplished so far is(although I'm not sure even if its correct):

sufficient(X, Y, M, N, F) :- 
    F is Y-X,
    Y>=X,
    plus(M, 1, N),
    sufficient(X, F, N, N, F).

I have problem finding my base case, I'm confused on how to implement it. Also, in the sufficient I have implemented, obviously when Y<X it terminates returning false. Is there a way to get the N and F before terminating? I am feeling that I am not thinking the "prolog" way, since I am mostly used on C and that vagues my thinking. Thanks.

EDIT 2

I have found my base case and I can stop recursion however, I can't manage to ge the correct values. My code:

sufficient(X, Y, M, N, F) :- Y<X.
sufficient(X, Y, M, N, F) :- 
   F is Y-X,
   plus(M, 1, N),
   sufficient(X, F, N, D, E).

Thing is after the first recursion, if for example I call sufficient as sufficient(10,21,0,N,F). from the swi prolog command prompt, I 'll get N=1 and F=11. That happens because I make 2 new variables D and E. If I don't make those 2 new variables(D and E), and at the 3rd sufficient in the code I call N and F instead of D and E at the line F is Y-X, I get a false, because F is 11 and Y-X is 1. Do I have to set the a subtraction function myself, since F is Y-X is not exactly a subtraction? Any ideas on how to do it?

Try [tag:successor-arithmetics] first! You can define addition there, which is the very same as subtraction! — false, Dec 02 '16 at 18:00
Take [`nat_nat_sum/3`](http://stackoverflow.com/q/27202175/772868): `nat_nat_dif(A, B, D) :- nat_nat_sum(B, D, A).` — false, Dec 03 '16 at 00:16
If X and Y are known, successor arithmetic won't be needed; `is` is sufficient. — Topological Sort, Dec 05 '16 at 13:10

score 4 · Accepted Answer · answered Dec 02 '16 at 17:41

4

All recursive functions need at least one base case. In what circumstance should your function say, OK, I have the answer, no need to recurse?

It would be the case in which your pseudocode loop is done, right?

Usually we write it in this format:

factorial(0,1).                          % The factorial of 0 is 1.
factorial(N,Factorial) :-
   N>0,                                   % You may need to test applicability 
                                          %    of this recursive clause
   NMinus1 is N-1,                        % maybe some setup
   factorial(NMinus1,FactorialOfNMinus1), %recursive call
   Factorial is N*FactorialOfNMinus1).    %and maybe some code after

I wouldn't want to do your homework for you, but this should get you going:

sufficient(X,Y,M,N,F) :- %whatever condition means you're done, 
                         % and results = whatever they should
sufficient(X,Y,M,N,F) :- %whatever condition means you aren't done
                         % and setting up results w/ a recursive call

One more hint: looks like M is a temporary variable and need not be a parameter.

answered Dec 02 '16 at 17:41

Topological Sort

2,733
2
27
54

Yeah M is a temporary variable. I removed it. However, I still can't see how the base case needs to be implemented. That's where im stuck for the past couple of days. If I implement it as `sufficient(X, Y, 0, F) :- Y>=X` it is obviously wrong, since if I call it the same way in the SWI-Prolog prompt, it won't even recurse. Can you provide some more tips ? Also, I have changed the second `sufficient` with the following: `sufficient(X, Y, N, F) :- F is Y-X, plus(N, 1, N), F is F+2, sufficient(X, F, N, F).` – tiempo Dec 02 '16 at 18:57
If you have a new version: edit your original post? When I try to compile your new version, I get a problem of a missing period on the first clause. When I fix that, I get a problem that `plus(N,1,N)` won't work (and I know that F is F+2 wont' work either), and this is likely your biggest issue: in PROLOG, like in logic, F=F+2 is nonsense: F _can't_ be 2 more than itself! If you want something that's 2 more than F it will need a new name. FPlus2 is F+2 will work. – Topological Sort Dec 02 '16 at 19:54
Ok! My bad! Gonna edit it in 10 minutes if you are interested. – tiempo Dec 02 '16 at 20:35
I may have to look at this again later, but for now, let me say: yes, `F is Y-X` is subtraction, and should work, as long as Y and X have values by the time you reach that line, which they should. – Topological Sort Dec 04 '16 at 20:28
When I run it now it complains it can't add 1 to M and get N because M has no value. As you point out, D and E aren't useful, because they don't relate in any way to the parameters passed in (X, Y, M, N, F). Based on the comments you made in your most recent edit, it seems you were considering passing in N and F, which means N and F would change values, but you can't have that. How should D and E relate to N and F? Put that in your code. (I won't specify how, but we know how F relates to Y and X above.) – Topological Sort Dec 04 '16 at 20:33
Getting an understanding of PROLOG variables is really what you need here, more than fixing a problem with this particular assignment. Here's a start: http://stackoverflow.com/questions/33503336/change-value-in-prolog (read the first answer). A PROLOG text as well. Short version: variable values in a function cannot change. They can be unassigned or can have values but those values never change. Also, if (say) NPlus1 is N+1, N must have a value already. – Topological Sort Dec 04 '16 at 20:42
Ok thanks. Unfortunately I lost my deadline, but your answer was really useful. Thanks for your time. Going to study the links you provided. – tiempo Dec 05 '16 at 08:24

Prolog recursive subtraction

1 Answers1