Division By Repeated Subtraction
May 12, 2017
I traded several emails this week with a programming student who was having trouble with this assignment:
Write a function that divides two numbers and returns their quotient. Use recursive subtraction to find the quotient.
The student went on to explain that he thought he needed to use a counter variable that he incremented each time the function recurred, but he didn’t know how to do that because the function could only take two arguments; it had to be of the form (define (divide a b) ...)
.
Your task is to write the function, and explain to the student how it works. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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, whena < b
. If this is so, then division will yield0
. If this is not the case, then we recursively call the method by noticing thata - b
has one lessb
‘s worth of magnitude thana
, meaning thatdivide(a, b) - divide(a - b, b) = 1
. We restructure the formula to get the recursive invocationdivide(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: