Win a copy of Java EE 8 High Performance this week in the Java/Jakarta EE forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

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

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.

Sheriff
Posts: 21208
87
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.

 It is sorta covered in the JavaRanch Style Guide.