CODEWITHSUNDEEP
recursionprologincrement
user2096383
user2096383

Reputation: 13

Prolog - making a recursive divisor

Okay, so I'm a beginner in Prolog so I'm sorry if I can't quite get my question across very clearly but this is where I'm struggling:

divide_by(X, D, I, R) :- (D > X), I is 0, R is X.

divide_by(X, D, I, R) :-
X >= D,
X_1 is X - D,
I_1 is I + 1,
divide_by(X_1, D, I_1, R),
R is X_1.

I'm trying to write a program that will accept two arguments (X and D) and return the Iterations (I) and Remainder (R) so that it can display the result of X / D when the user enters: divide_by(8,3,I,R). for example.

When tracing the code I know that I is incorrect because the first increment makes it equal to 0 and so the count for that is wrong. But I don't know how to declare I is 0 without it resetting every time it recurses through the loop. (I don't want to declare I as 0 in the query)

I also realised that when it has finished recursing (when X < D) then I is going to be set to 0 because of the base case.

Would anyone be kind enough to show me how I can fix this?

Upvotes: 1

Views: 625

Answers (1)

Nicholas Carey
Nicholas Carey

Reputation: 74277

You need to introduce an accumulator and use a helper predicate, something like this:

divide(_,0,_,_) :- !, fail . % X/0 is undefined and so can't be solved.
divide(0,_,0,0) :- !.        % 0/X is always 0.
divide(X,Y,Q,R) :-           % the ordinary case, simply invoke the
  divrem(X,Y,0,Q,R)          % helper with the accumulator seeded with 0
  .

divrem(X,Y,Q,Q,X) :-   % if X < Y, we're done.
  X < Y .              %
divrem(X,Y,T,Q,R) :-   % otherwise...
  X >= Y ,             % as long as X >= Y,
  X1 is X - Y ,        % compute the next X
  T1 is T + 1 ,        % increment the accumulator
  divrem(X1,Y,T1,Q,R)  % recurse down
  .                    % Easy!

Upvotes: 1

Related Questions