Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Trying to figure out recursive algorithm to find greatest common divisor of two integers

Greg Stevens
Ranch Hand
Posts: 41
I have not searched the forums on this because I want to try to work out as much of this on my own as I can.
I know how to solve this with with a loop. If the the larger integer can be divided by the smaller integer with a remainder
of 0, then the smaller integer is the greatest common divisor. Otherwise, iterate from (smaller - 1) down to 1 and check
for divisibility for both larger and smaller integer.

I know I should be thinking in terms of a base case and a simplification of the original problem, but I don't see it.

Any small hint?

Greg Stevens
Ranch Hand
Posts: 41
I remember now that the solution is the Euclidean algorithm. Never mind. I will try some other recursive problem.

Rob Spoor
Sheriff
Posts: 20531
54
Here's the general non-recursive algorithm:
Now try and convert that into a recursive call. You already have the finished condition: max % mid == 0. Another possibility is a == b.

To make it easier, the first step can be to make sure that a is larger than b:
Hint: the actual Euclidian algorithm described here already is a recursive call, with the finished condition being b == 0.