# GCD Algorithm: Greatest Common Divisor in Java

Here are three different implementations of the classic GCD (Greatest Common Divisor) problem.

## Iterative (Linear)

It wouldn’t make sense to ever implement the iterative linear approach due to its time complexity, but I’ve included it anyway.

```    /**
* Linear GCD method.
*
* @param a
* @param b
* @param b
* @param i The number of iterations performed.
*
* @return GCD between a and b.
*/
public static int gcd_linear(int a, int b, int i)
{
// Store the initial divisor check.
int divisor = b;

// Iterate through the divisor, decrementing downwards.
while(divisor >= 1){
// Check if a and b are divisible by the divisor.
if(a % divisor == 0 && b % divisor == 0){

// We have the GCD.
return divisor;

}
// Decrement the divisor.
divisor--;
// Increment iterations.
i++;
}

// We should never reach this point, but we put this
// to satisfy the compiler. Either way, it would logically make
// sense to return 1.
return 1;
}
```

## Recursive

The recursive algorithm is the simplest in it’s form, but the recursive calls on a large input will clog up the stack.

```    /**
* Recursive method to finding the GCD.
*
* @param a
* @param b
* @param i The number of iterations performed.
*
* @return GCD between a and b.
*/
public static int gcd_rec(int a, int b, int i)
{
// If b = 0, return a.
if(b == 0){

// Return the gcd.
return a;
}

// Recursively call, and increment iterations.
return gcd_rec(b, a % b, ++i);
}
```

## Iterative (Euclid’s Algorithm)

Therefore, the iterative approach using Euclid’s algorithm is probably the best way to go in terms of real-world implementation.

```    /**
* Iterative method to finding the GCD, using Euclid's algorithm.
*
* @param a
* @param b
* @param i The number of iterations performed.
*
* @return GCD between a and b.
*/
public static int gcd_iter(int a, int b, int i)
{
// Store remainder.
int remainder;

// Check for gcd.
do {
remainder = a % b;
a = b;
b = remainder;
// Increment iterations.
i++;
} while (remainder > 0);

// Return the gcd.
return a;
}
```

If you want to test the performance of these algorithms, print the `i` parameter in each of the functions to see how many iterations were performed in calculating the GCD.