Home » Java » Java Programs

Java program to calculate the Highest Common Factor of two numbers using recursion

Given two numbers, we have to calculate the Highest Common Factor of them using the recursion.
Submitted by Nidhi, on June 02, 2022

Problem Solution:

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

Program/Source Code:

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

// Java program to calculate the Highest Common Factor 
// of two numbers using the recursion

import java.util.*;

public class Main {
  public static int calculateHCF(int num1, int num2) {
    while (num1 != num2) {
      if (num1 > num2)
        return calculateHCF(num1 - num2, num2);
      else
        return calculateHCF(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 = calculateHCF(num1, num2);
    System.out.printf("HCF is: " + res);
  }
}

Output:

Enter number1: 45
Enter number2: 75
HCF is: 15

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 calculateHCF(), main(). The calculateHCF() is a recursive method that finds the HCF 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 calculateHCF() method to calculate the Highest Common Factor of input numbers and printed the result.

Java Recursion Programs »

---