Home » Java » Java Programs

Java program to calculate the Greatest Common Divisor of two numbers using recursion

Given two numbers, we have to calculate the Greatest Common Divisor of them using the recursion.
Submitted by Nidhi, on June 03, 2022

Problem statement

In this program, we will read two integer numbers from the user and then we will calculate the Greatest Common Divisor of given numbers using recursion.

Java program to calculate the Greatest Common Divisor of two numbers using recursion

The source code to calculate the Greatest Common Divisor of two numbers using recursion is given below. The given program is compiled and executed successfully.

// Java program to calculate the Greatest Common Divisor 
// of two numbers using recursion

import java.util.*;

public class Main {
  public static int calGCD(int num1, int num2) {
    while (num1 != num2) {
      if (num1 > num2)
        return calGCD(num1 - num2, num2);
      else
        return calGCD(num1, num2 - num1);
    }
    return num1;
  }

  public static void main(String[] args) {
    Scanner X = new Scanner(System.in);

    int num1 = 0;
    int num2 = 0;
    int res = 0;

    System.out.printf("Enter number1: ");
    num1 = X.nextInt();

    System.out.printf("Enter number2: ");
    num2 = X.nextInt();

    res = calGCD(num1, num2);
    System.out.printf("GCD is: " + res);
  }
}

Output

Enter number1: 12
Enter number2: 9
GCD is: 3

Explanation

In the above program, we imported the "java.util.*" package to use the Scanner class. Here, we created a public class Main. The Main class contains two static methods calGCD() and main(). The calGCD() is a recursive method that finds the GCD of two numbers and returns the result to the calling method.

The main() method is the entry point for the program. Here, we read two integer numbers from the user and called the calGCD() method to calculate the Greatest Common Divisor of input numbers and printed the result.

Java Recursion Programs »

---