/**
 * Recursion example implmenting Euclid's algorithm for greatest common
 * denominator of two numbers
 * @author Hyrum D. Carroll
 * @version 0.2 (November 4, 2019)
 */
public class GCD{

    /**
     * Euclidean algorithm for calculating the greatest common denominator
     * (GCD) of two numbers.
     * @param a one of the two numbers
     * @param b one of the two numbers
     * @return the greatest common denominator of a and b
     *         (meaning the largest number that divides both a and b without
     *          a reminder)
     */
    public static long gcd( long a, long b ){
        System.out.println( "gcd("+a+","+b+")");

        if( b == 0 ){
            // base case
            return a;
        }else{
            return gcd( b, a % b );
        }
    }

    public static void main( String[] args ){
        long num1 = 100;
        long num2 = 8;
        long result = gcd( num1, num2 );
        System.out.println("gcd("+num1+","+num2+")="+result+" (in main)\n");

        num1 = 8;
        num2 = 100;
        result = gcd( num1, num2 );
        System.out.println("gcd("+num1+","+num2+")="+result+" (in main)\n");

        num1 = 200;
        num2 = 13;
        result = gcd( num1, num2 );
        System.out.println("gcd("+num1+","+num2+")="+result+" (in main)\n");
    }
}