Java Code Example: greatest common divisor (recursion)

The code is an implementation of the Euclidean algorithm for finding the greatest common divisor (GCD) of two numbers. The gcd method is a recursive function that takes two integers a and b as input, and returns the GCD of the two numbers. The method first checks if either a or b is equal to 0. If either a or b is 0, then the other number is returned as the GCD. If both a and b are greater than 0, then the method subtracts the smaller number from the larger number and calls the gcd method recursively with the two new numbers until one of the numbers becomes 0, at which point the other number is returned as the GCD. Finally, the main method calls the gcd function with a=120 and b=45, and prints the result.

public class GreatestCommonDivisor {
    static int gcd(int a, int b) {
        if (a == 0) {
            return b;
        } else if (b == 0) {
            return a;
        } else if (a > b) {
            return gcd(a - b, b);
        } else {
            return gcd(a, b - a);
        }
    }

    public static void main(String[] args) {
        int a = 120, b = 45;

        System.out.println("Greatest common divisor is: " + gcd(a, b));
    }
}

Output

Greatest common divisor is: 15