/**
 * In mathematics, the greatest common divisor (gcd) of two or more integers, when at least one of them is not 
 * zero, is the largest positive integer that is a divisor of both numbers.  
 * 
 * @see <a href="https://en.wikipedia.org/wiki/Greatest_common_divisor">Greatest Common Divisor (Wikipedia)</a>
 */
public class GreatestCommonDivisor {

    /**
     * Calculate greatest common divisor of two numbers using recursion. 
     */
    public static long gcdUsingRecursion(long a, long b) {
        a = Math.abs(a);
        b = Math.abs(b);
        return a == 0 ?  b : gcdUsingRecursion(b%a, a);
    }

    /**
     * A much more efficient method is the Euclidean algorithm, which uses a division algorithm such as long division 
     * in combination with the observation that the gcd of two numbers also divides their difference. 
     * @see <a href="https://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid.27s_algorithm">Euclidean Algorithm (Wikipedia)</a>
     */
    public static final long gcdUsingEuclides(long x, long y) {
        long greater = x;
        long smaller = y;
        if (y > x) {
            greater = y;
            smaller = x;
        }

        long result = 0;
        while (true) {
            if (smaller == greater) {
                result = smaller; // smaller == greater
                break;
            }

            greater -= smaller;
            if (smaller > greater) {
                long temp = smaller;
                smaller = greater;
                greater = temp;
            }
        }
        return result;
    }
}
