## Division By Repeated Subtraction

### May 12, 2017

I imagine most of my readers can write the requested function. But it was enlightening to me to see the problems my student had understanding recursion, which is natural to me. Here’s the function he wanted (we assume no negative numbers):

(define (divide n d) (if (< n d) 0 (+ (divide (- n d) d) 1))) > (divide 29 4) 7

I also showed him this function, which keeps a counter as he originally wanted to do:

(define (divide n d) (define (divide-helper q r) (if (< r d) (values q r) (divide-helper (+ q 1) (- r d))))) (divide-helper 0 n)) > (divide 29 4) 7

We went back and forth through a couple of rounds of emails, but what eventually made him understand how it worked was when I asked what happened when he evaluated `(divide 29 0)`

. When he finally realized that the recursion never stopped because *n* was never decremented, he finally *got* recursion.

As I said, the interaction was enlightening, and it was also rewarding to help a student get across the mental barrier that prevented him from understanding a new concept.

You can run the program at http://ideone.com/A6XJoS.

Pages: 1 2

Nice story, especially how division by zero helped :)

Division itself is a bit of a distraction when it’s not specified that the numbers are non-negative integers, so I spent some time worrying about that, but what bothered me most was not being able to use three arguments when implementing a function that takes two. One must get over that. So I wrote the following. I make no attempt to explain recursion.

@Jussi: Division by zero was the clincher. When the student realized that the computation failed because recursion never reached the base case, he finally understood the true meaning of the base case, and how it makes everything work.

@Praxis: Yes, I understood that. Note that I followed your rules and wrote my program and its comments before reading your solution.

Negative numbers might have a similar effect, possibly even more so: there would be cases where the computation “progresses” but in the wrong direction, away from the base case.

C11 solution:

#include <stdio.h>

#include <stdlib.h>

int

divide (int a, int b);

int

main (int argc, char **argv)

{

const int a = 15;

const int b = 4;

printf("%d / %d = %d\n", a, b, divide(a, b));

exit(0);

}

`int`

divide (int a, int b)

{

if (a < b)

return 0;

else

return 1 + divide(a - b, b);

}

We build

`divide`

by asking what the base case is: in our case, when`a < b`

. If this is so, then division will yield`0`

. If this is not the case, then we recursively call the method by noticing that`a - b`

has one less`b`

‘s worth of magnitude than`a`

, meaning that`divide(a, b) - divide(a - b, b) = 1`

. We restructure the formula to get the recursive invocation`divide(a - b, b) + 1`

.Gforth:

[sourcecode]

: / over over < IF 0 ELSE swap over – swap recurse 1 + THEN ;

[/sourecode]

Which language is that? It seems very foreign to me.

Here is a Haskell version. The Natural number type represents unbounded, non-negative integers.

Sample output from the REPL:

buoyantair: The language you asked about is Forth.

Firstly, we need to remember that if is then is undefined, and so we need to specify that the function will return not only the quotient and the remainder of but also whether is undefined:

Secondly, we also need to remember that may be positive or negative (or zero) and that may be positive or negative, and so to function correctly regardless of the signs of and whilst remaining simple the function will first determine if the quotient will be negative (if either or – but not both – is negative) and will use the absolute values of and thereafter…

…setting the quotient to be negative (if necessary) just before it is returned:

Let’s specify that the base cases of the function –

viz., the cases wherein the function will not invoke itself – are the cases where either is greater than (and so the quotient and remainder of are and , respectively) or where is (and so is undefined):The remaining non-base case of the function –

viz., the case wherein the function will invoke itself – is the case where is greater than- or equal to- ; we know that:in that case the quotient is at least ;

in that case the function will invoke itself and will pass to itself as an argument a dividend of not but of ;

and that the function invoked in 2. will return a data structure containing the quotient and remainder of and whether is undefined.

And so, given 1. and 3., the function will increment the quotient in the data structure returned to it after 2.:

And the following is the complete function:

(I hope that the above is comprehensible; although I’m interested in teaching – and more specifically in improving the teaching and assessment of GCSEs and AS & A levels in the STEM subjects and in making the teaching and assessment of those qualifications available to more students (more specifically to students who are studying at secondary schools or sixth form colleges which don’t offer those qualifications or who are, like myself, not in education) – I’m not, and have never been, a teacher or anything approaching that :/ )