Greatest Common Divisor GCD Implementation Recursive and Iterative in Java

The greatest common divisor (gcd) of two integers is the largest positive integer that divides the numbers without a remainder.

For example, the GCD of 8 and 12 is 4.

package basics;

public class GCD {

 public static long gcdRecursive(long a, long b) {
  
  if (a == 0)
   return b;
  if (b == 0)
   return a;
  if (a > b)
   return gcdRecursive(b, a % b);
  
  return gcdRecursive(a, b % a);
 }

 public static long gcdIterative(long m, long n) {
  
  while ( m!=0 && n != 0 ) {
   long remainder = m % n;
   m = n;
   n = remainder;
  }
  return m+n;
 }
 
 public static void main(String[] args) {
  
  System.out.println("Recursive GCD of 50 and 0 = "+gcdRecursive(50,0));
  System.out.println("Recursive GCD of 0 and 50 = "+gcdRecursive(0,50));
  System.out.println("Recursive GCD of 50 and 10 = "+gcdRecursive(50,10));
  System.out.println("Recursive GCD of 40 and 9 = "+gcdRecursive(40,9));
  System.out.println("Recursive GCD of 8 and 12 = "+gcdRecursive(8,12));
  System.out.println();
  
  System.out.println("Iterative GCD of 50 and 0 = "+gcdIterative(50,0));
  System.out.println("Iterative GCD of 0 and 50 = "+gcdIterative(0,50));
  System.out.println("Iterative GCD of 50 and 10 = "+gcdIterative(50,10));
  System.out.println("Iterative GCD of 40 and 9 = "+gcdIterative(40,9));
  System.out.println("Iterative GCD of 8 and 12 = "+gcdRecursive(8,12));
 }

}

Create a GCD.java file in your workspace.

When the main method inside the GCD class executed it is going to print :

Recursive GCD of 50 and 0 = 50
Recursive GCD of 0 and 50 = 50
Recursive GCD of 50 and 10 = 10
Recursive GCD of 40 and 9 = 1
Recursive GCD of 8 and 12 = 4


Iterative GCD of 50 and 0 = 50
Iterative GCD of 0 and 50 = 50
Iterative GCD of 50 and 10 = 10
Iterative GCD of 40 and 9 = 1
Iterative GCD of 8 and 12 = 4


References :

Data Structures and Algorithm Analysis in Java (3rd Edition)

Wikipedia = Greatest Common Divisor