Slide 6.a: Recursive greatest common divisor (GCD)

Greatest Common Divisor (GCD)

In mathematics, the GCD of two integers is the largest positive integer that divides each of the integers. For two integers, x and y, the greatest common divisor of x and y is denoted by gcd(x, y). For example, the GCD of 8 and 12 is 4, that is, gcd(8,12)=4.

Several GCD algorithms are available. The one on the right uses recursion and is concise.

1function gcd( int a, int b )
2  if ( b == 0 )
3    return a
4  else
5    return gcd( b, a mod b )
6  end if
7end function

RecursiveGCD.java (recursive greatest common divisor)

 // Recursive Java program to find the GCD 
 class RecursiveGCD {
   public static void main( String[ ] args ) {
     // Find GCD between two command-line arguments.
     int a = Integer.parseInt( args[0] );
     int b = Integer.parseInt( args[1] );
     System.out.print( "GCD of " + a + " and " + b + " is " );
     a = Math.abs( a );
     b = Math.abs( b );

     // Check the special cases.
     if ( ( a == 0 ) && ( b == 0 ) )  System.out.println( 0 );
     else if ( b == 0 )  System.out.println( a );
     else if ( a == 0 )  System.out.println( b );
     else  recursiveGCD( a, b );
   }

   static void recursiveGCD( int a, int b ) {
     if ( b == 0 )  System.out.println( a );
     else           recursiveGCD( ,  );
   }
 }

shell> java RecursiveGCD