GCD recursion java - Java Program to Find Greatest Common Divisor (GCD) of Two Numbers by Using Recursion

Prerequisite: Recursion in Java

GCD recursion java: In the previous article, we have discussed about Java Program to Convert Decimal to Binary Using Recursion

In this program we are going to see how to find GCD of 2 numbers using Recursion by Java programming language.

Java Program to Find Greatest Common Divisor (GCD) of Two Numbers by Using Recursion

Explanation:

Find gcd java: A method calling itself is called as recursive method, and the technique is known as recursion.

Lets assume 2 numbers A = 10, B=15

So the GCD(10,15) = 5

Factor of 10 = 1,2,5,10

Factors of 15 = 1,3,5,15

Common factors of 10,15 = 1,5

Hence GCD(10,15) = 1*5 = 5

Now let’s see different ways to find find GCD of 2 numbers in an Array by using Recursion.

By Using Static Input and Recursion
By Using User Input and Recursion

Method-1: Java Program to Find Greatest Common Divisor (GCD) of Two Numbers By Using Static Input and Recursion

Approach:

Declare and initiate an integer variable ‘a’ as 10
Declare and initiate an integer variable ‘b’ as 15
Call a user defined method calculateGCD() and pass the ‘a’,‘b’ as parameter.
Inside the user defined method, check if the 2nd number is zero or not. If the 2nd number is 0 then return a, else call the same method as “calculateGCD(b, a%b)” and return the value to the main method.
Now the value of the user defined method calculateGCD() is stored in an integer variable say ‘gcd’.
Print the gcd of 2 numbers.

Program:

import java.util.*;
import java.io.*;
public class Main 
{
    public static void main(String[] args)
    {
        //declare and initialize an integer variable a
        int a = 10;
        //declare and initialize an integer variable b
        int b = 15;
        //call the method and store the value inside an integer variable say ‘gcd’
        int gcd = calculateGCD(a,b);
        //print the result
        System.out.println("The GCD of two numbers "+a+", "+b+" is: "+gcd);
    }
    
    //calculateGCD() method
    static int calculateGCD(int a, int b)
    {
        // check if b is not equal to 0 then call the method recursively. Else return a
        if (b != 0)
            //calling the method recursively
            return calculateGCD(b, a%b);
        else
            return a;
    }
}

Output:

The GCD of two numbers 10, 15 is: 5

Method-2: Java Program to Find Greatest Common Divisor (GCD) of Two Numbers by Using Recursion By Using User Input and Recursion

Approach:

Create object scanner class.
Declare two integer variables say ‘a’ and ‘b’
Prompt the user to enter the valuess for ‘a’ and ‘b’ respectively.
Call a user defined method calculateGCD() and pass the ‘a’,‘b’ as parameter.
Inside the user defined method, check if the 2nd number is zero or not. If the 2nd number is 0 then return a, else call the same method as “calculateGCD(b, a%b)” and return the value to the main method.
Now the value of the user defined method calculateGCD() is stored in an integer variable say ‘gcd’.
Print the gcd of 2 numbers.

Program:

import java.util.*;
import java.io.*;
public class Main 
{
    public static void main(String[] args)
    {
        // create scanner class object
        Scanner s = new Scanner(System.in);
        System.out.println("Enter the 1st number:");
        //declare an integer variable ‘a’ and take the value as user input 
        int a = s.nextInt();
        System.out.println("Enter the 2nd number:");
        //declare an integer variable ‘b’ and take the value as user input 
        int b = s.nextInt();
        //call the method and store the value inside an integer variable say ‘gcd’
        int gcd = calculateGCD(a,b);
        //print the result
        System.out.println("The GCD of two numbers "+a+", "+b+" is: "+gcd);
    }
    
    //calculateGCD() method
    static int calculateGCD(int a, int b)
    {
        // check if b is not equal to 0 then call the method recursively. Else return a
        if (b != 0)
            //calling the method recursively
            return calculateGCD(b, a%b);
        else
            return a;
    }
}

Output:

Enter the 1st number:
78
Enter the 2nd number:
97
The GCD of two numbers 78, 97 is: 1

If you are new to Java and want to learn the java coding skills too fast. Try practicing the core java programs with the help of the Java basic programs list available.

Related Java Programs: