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.