# Euclidean algorithm (Java, recursive)

(Redirected from Euclid's Algorithm (Java))
Other implementations: C | Erlang | Forth | Haskell | Java | Java, recursive | OCaml | Prolog | Python | Scala | Standard ML

The Euclidean algorithm is an efficient method for computing the greatest common divisor of two natural numbers (or polynomials, or any other object with the necessary structure), and was one of the first known algorithms to be described formally. It is based on the two identities:

a > b implies: gcd(a, b) = gcd(b, a mod b)
gcd(a, 0) = a

This article describes a recursive Java implementation of the algorithm.

The gcd method requires that a and b are positive integers and that a > b.

```<<gcd method>>=
public static long gcd(long a, long b)
{
base case
general case
}
```

The base case applies when b is equal to 0:

```<<base case>>=
if (b == 0) return a;
```

Since a > b, the first identity can be used for the general case:

```<<general case>>=
else return gcd(b, a % b);
```

## Sample code and demonstration

Here's some code demonstrating how to use the above method:

```<<Euclid.java>>=
public class Euclid
{
gcd method
public static void main(String[] args)
{
long n0 = Long.parseLong(args);
long n1 = Long.parseLong(args);
long res;
if (n0 > n1)
res = gcd(n0, n1);
else if (n1 > n0)
res = gcd(n1, n0);
else
res = n0;
System.out.println(res);
}
}
```

If we compile and run the following command lines:

```java Euclid 35 42
java Euclid 35 40
java Euclid 35 38
```

We get the following outputs:

```7
5
1
```