-3

Euclid's algorithm tells us how to compute the greatest common divisor (GCD) of two positive integers a and b. Using Euclid's algorithm, to find the GCD of 206 and 40 (for example), first find the remainder when 206 is divided by 40. Then find the GCD of 40 and this remainder (which turns out to be 6), using the same idea again. When you reach the point where the second number is 0, the first number will be the GCD of 206 and 40 that you were looking for, as shown below.

gcd(206, 40)
= gcd(40, 6)
= gcd(6, 4)
= gcd(4, 2)
= gcd(2, 0)
= 2

Write a method called gcd. YOU MUST USE RECURSION IN THIS METHOD (calling the method within the method). This method should use Euclid's algorithm to return the greatest common divisor of two positive integers.

So basically I don't know how to do this WITH (sorry i wrote without before on accident) recursion.. Please help! :( I have been stuck on this for so long.. I wrote a method, but it doesn't use recursion and it only woks for the given 206 and 40..

Prashant Kumar
  • 20,069
  • 14
  • 47
  • 63
user2776991
  • 17
  • 1
  • 5
  • 1
    possible duplicate of [Java: get greatest common divisor](http://stackoverflow.com/questions/4009198/java-get-greatest-common-divisor) – Paul Vargas Sep 13 '13 at 15:27
  • 3
    Show us the method you wrote. – Surveon Sep 13 '13 at 15:28
  • 3
    I'm voting this question down because it's just a well-hidden "gimme teh codez". A recursive Java implementation of GCD is just one Google-request away. – fvu Sep 13 '13 at 15:30
  • Wait wait wait, you need to use recursion, but you don't know how to do it **without** recursion? Then what's the problem? Use recursion like you're supposed to. Or do you mean that you don't know how to do it **with** recursion? – thegrinner Sep 13 '13 at 15:34
  • Please edit the question back to how it was!!! – huMpty duMpty Sep 13 '13 at 15:50

1 Answers1

4

This is simple to implement using recursion:

public int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

The algorithm is explained in this Wikipedia page.

Óscar López
  • 232,561
  • 37
  • 312
  • 386