Java Program to find GCD of two Numbers using Recursion

GCD or Greatest Common Divisor, is a very important mathematical concept. It is used to find the largest positive integer that divides each number without leaving a remainder. Here in this post, we will learn how to write Java Program to find the GCD of two numbers using recursion in Java.

For Example:

We have two numbers, 12 and 18.

Here we will be using the Euclidean algorithm:

• First, we will divide 18 by 12, and get the remainder of 6. So the GCD of 12 and 18 is equal to the GCD of 6 and 12.
• Now We divide 12 by 6, which gives a remainder of 0. So the GCD of 6 and 12 is 6.

The output will be a GCD of 12 and 18 is 6.

Program 1: Using a Recursive Function

public class Main {

    public static int calculateGCD(int num1, int num2) {
        if (num2 == 0) {
            return num1;
        }
        return calculateGCD(num2, num1 % num2);
    }

    public static void main(String[] args) {
        int num1 = 12;
        int num2 = 18;
        int gcd = calculateGCD(num1, num2);
        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + gcd);
    }
}

Output

GCD of 12 and 18 is: 6

Explanation

In the above program, we have a class Main. We then defined a static method calculateGCD with two parameters of integers type num1 and num2. This method is a recursive method that will call itself again and again to calculate GCD. In this method, We check if num2 is equal to 0. If it is, we return num1 as the GCD. If it is not, we call the calculateGCD function recursively with num2 as the first argument and the remainder of num1 divided by num2 as the second argument. This process will be repeated until the remainder is 0. Remainder zero means we return the last non-zero remainder as the GCD.

Program 2: Using a ternary operator

This program will involve using a ternary operator to find the GCD of two numbers along with a recursive approach.

public class Main {

    public static int calculateGCD(int num1, int num2) {
        return (num2 == 0) ? num1 : calculateGCD(num2, num1 % num2);
    }

    public static void main(String[] args) {
        int num1 = 12;
        int num2 = 18;
        int gcd = calculateGCD(num1, num2);
        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + gcd);
    }
}

Output

GCD of 12 and 18 is: 6

Explanation

In the above program, there is a recursive method name calculateGCD that takes two integers, num1, and num2, as input. Here we will be using the ternary operator to check if num2 is equal to 0. If the value of num2 is zero we will return num1 as the GCD. If the value of num2 is not zero then we will call calculateGCD recursively with num2 as the first argument and the remainder of num1 divided by num2 as the second argument. These steps will be repeated until the remainder becomes 0, at which point we return the last non-zero remainder as the GCD.

Conclusion

In the above tutorial, we learned about writing Java programs to calculate or find the GCD of two given integers using recursion. Hope this tutorial helped you in learning the program.