aspose file tools*
The moose likes Beginning Java and the fly likes Trying to figure out recursive algorithm to find greatest common divisor of two integers Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Trying to figure out recursive algorithm to find greatest common divisor of two integers" Watch "Trying to figure out recursive algorithm to find greatest common divisor of two integers" New topic
Author

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

Greg Stevens
Ranch Hand

Joined: Jul 23, 2009
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

Joined: Jul 23, 2009
Posts: 41
I remember now that the solution is the Euclidean algorithm. Never mind. I will try some other recursive problem.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19543
    
  16

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.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Trying to figure out recursive algorithm to find greatest common divisor of two integers
 
Similar Threads
factors problem
Generating compound interest with integers
GCD/LCM problems
sorting fractions problem
Converting a double value to a fraction