Java Program to Find G.C.D Using Recursion

May 25, 2023

What is Recursion?

Recursion is a Process in which a Function can call itself directly and sometimes indirectly. The Function calling itself, again and again, is known as the Recursive Function.
We can solve certain complex problems quite easily using recursive algorithms like inorder and preorder traversals and many more.

In this Article, we will write a program to Find G.C.D Using Recursion.

Recursion in Java :

Recursion in Java is a programming technique where a method calls itself repeatedly until a termination condition is met. The termination condition is necessary to avoid an infinite loop. In Java, recursion is often used to solve problems that can be divided into smaller sub-problems, such as computing the factorial of a number, searching an element in an array, or traversing a tree data structure. To implement recursion in Java, you need to define the base case and the recursive case. The base case provides the stopping condition, while the recursive case defines the logic for breaking down the problem into smaller sub-problems.

What is GCD (Greatest Common Divisor)?

The G.C.D (Greatest Common Divisor) is the largest positive integer that divides two or more integers without leaving a remainder. It is a commonly used mathematical concept in number theory and algebra. The G.C.D of two or more numbers can be found using various algorithms, such as the Euclidean algorithm.

Example :

GCD of 12 and 8 is 4, since 4 is the largest number that divides both 12 and 8.
GCD of 24 and 18 is 6, since 6 is the largest number that divides both 24 and 18.

Program to calculate GCD of a Number Without Recursion :

Run

// Importing all the required packages 
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    // Scanner class for taking imputs
    Scanner sc = new Scanner(System.in);
    System.out.print("Enter two numbers: ");
    
    // Taking inputs of the two required variables 
    int num1 = sc.nextInt();
    int num2 = sc.nextInt();

    // ans element
    int gcd = 1;
    int k = 2;
    
    // while loop to find the GCD
    while (k <= num1 && k <= num2) {
      if (num1 % k == 0 && num2 % k == 0) {
        gcd = k;
      }
      k++;
    }
    System.out.println("GCD of " + num1 + " and " + num2 + " is: " + gcd);
  }
}

Output:

Enter two numbers: 12 8
GCD of 12 and 8 is: 4

Explanation :

The above program uses a while loop to iterate through all the integers from 2 to the minimum of the two input numbers. At each iteration, it checks if both numbers are divisible by the current value of k. If they are, the value of gcd is updated to k. The final value of gcd after the loop is the G.C.D of the two numbers.

Program to calculate GCD of a Number using Recursion :

Run

// Importing all the required packages 
import java.util.Scanner;

public class Main {
  public static void main(String[] args){
    // Scanner class for taking inputs
    Scanner sc = new Scanner(System.in);
    System.out.print("Enter two numbers: ");
    int num1 = sc.nextInt();
    int num2 = sc.nextInt();

    // Recursive Function calling 
    int gcd = gcd(num1, num2);
    System.out.println("GCD of " + num1 + " and " + num2 + " is: " + gcd);
  }
  
  // Recursive function definition
  public static int gcd(int num1, int num2){
    // Base case  
    if (num2 == 0) {
      return num1;
    }
    return gcd(num2, num1 % num2);
  }
}

Output:

Enter two numbers: 12 8
GCD of 12 and 8 is: 4

Explanation:

The above program uses the Euclidean algorithm to calculate the GCD of two numbers using recursion. The function gcd takes two numbers as inputs and returns their GCD. The function uses the following logic: if the second number is 0, then the GCD is equal to the first number. Otherwise, the GCD is equal to the GCD of the second number and the remainder of dividing the first number by the second number.

This logic is implemented in the return statement of the function. The function calls itself with the two updated arguments until the second argument is 0, at which point it returns the first argument, which is the GCD.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others