This week's book giveaway is in the Design forum.
We're giving away four copies of Design for the Mind and have Victor S. Yocco on-line!
See this thread for details.
Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

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

 
Greg Stevens
Ranch Hand
Posts: 41
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I remember now that the solution is the Euclidean algorithm. Never mind. I will try some other recursive problem.
 
Rob Spoor
Sheriff
Pie
Posts: 20511
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic