Java Program to Find HCF of Two Numbers Using Recursion

by

In this article we are going to see how we can find HCF of two numbers using recursion by Java programming language.

Java Program to Find HCF of Two Numbers Using Recursion

HCF: 

HCF refers to the Highest Common Factor which refers to the largest common factor between 2 or more numbers.

It is also called Greatest Common Factor (GCF) or Greatest Common Divisor (GCD).

For example-

Two numbers are 2 and 4. Then the HCF is 2.
Two numbers are 30 and 42. Then the HCF is 6.

Let’s see the program to understand it clearly.

Method-1: Java Program to Find HCF of Two Numbers Using Recursion By Using Static Input Value

Approach:

  • Store two numbers in two integer variables.
  • Call the user defined method hcfCalculator( ) to find the product and store it. The method checks if either the numbers are zeroes or are equal to each other then it calculates hcf by taking modulus of the larger number and calling the method again.
  • Print the result.

Program:

import java.util.*;
// Main class
public class Main
{
    // Recursive method to find hcf of two numbers
    public static int hcfCalculator(int num1, int num2)
    {
        // cHecks if num1 and num2 are same numbers
        if (num1 == num2) 
        {
            return num1;
        // Checks if wither of the numbers are zeroes
        } 
        else if (num1 == 0) 
        {
            return num2;
        } 
        else if (num2 == 0) 
        {
            return num1;
        // Finds the hcf using recursin
        } 
        else if (num1 > num2) 
        {
            return hcfCalculator(num1 % num2, num2);
        } 
        else 
        {
            return hcfCalculator(num1, num2 % num1);
        }
    }
    
    public static void main(String[] args)
    {
        int num1 = 39, num2 = 62;
        // Call the method and store the result
        int hcf = hcfCalculator(num1,num2);
        // Print the result
        System.out.println("The hcf of "+num1+" and "+num2+" is "+hcf);
    }
}


Output:

The hcf of 39 and 62 is 1

Method-2: Java Program to Find HCF of Two Numbers Using Recursion By Using User Input Value

Approach:

  • Ask the user to enter two numbers in order.
  • Store two numbers in two integer variables.
  • Call the user defined method hcfCalculator( ) to find the product and store it. The method checks if either the numbers are zeroes or are equal to each other then it calculates hcf by taking modulus of the larger number and calling the method again.
  • Print the result.

Program:

import java.util.*;
// Main class
public class Main
{
    // Recursive method to find hcf of two numbers
    public static int hcfCalculator(int num1, int num2)
    {
        // cHecks if num1 and num2 are same numbers
        if (num1 == num2) 
        {
            return num1;
        // Checks if wither of the numbers are zeroes
        }
        else if (num1 == 0) 
        {
            return num2;
        }
        else if (num2 == 0) 
        {
            return num1;
        // Finds the hcf using recursin
        } 
        else if (num1 > num2) 
        {
            return hcfCalculator(num1 % num2, num2);
        } 
        else 
        {
            return hcfCalculator(num1, num2 % num1);
        }
    }
    
    public static void main(String[] args)
    {
        // Taking user input
        Scanner sc = new Scanner(System.in);
        // Ask the user to enter two numbers
        System.out.print("Enter two numbers to find HCF ");
        int num1 = sc.nextInt(), num2 = sc.nextInt();
        // Call the method and store the result
        int hcf = hcfCalculator(num1,num2);
        // Print the result
        System.out.println("The hcf of "+num1+" and "+num2+" is "+hcf);
    }
}


Output:

Enter two numbers to find HCF 10 5
The hcf of 10 and 5 is 5

Provided list of Simple Java Programs is specially designed for freshers and beginners to get familiarize with the concepts of Java programming language and become pro in coding.