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

Greg Stevens

Ranch Hand

Posts: 41

posted 6 years ago

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?

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

posted 6 years ago

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.

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.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions