Write a Java Program to Find G.C.D Using Recursion

In Java programming language, it is very common to find the greatest common divisor (GCD) of two integers.

The GCD is the largest positive integer that divides both numbers without leaving any remainder.

One approach to finding the GCD is through recursion.

In this tutorial, we will discuss how to find GCD using recursion in Java.

Recursion is a technique in programming where a function calls itself to solve a problem.

To find GCD using recursion, we can use the Euclidean algorithm.

The algorithm states that the GCD of two numbers is the same as the GCD of the smaller number and the remainder of the larger number divided by the smaller number.

The algorithm is repeated until the remainder is zero.

Here is the Java code to find GCD using recursion:

public class GCDRecursion {

    public static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        }
        else {
            return gcd(y, x % y);
        }
    }

    public static void main(String[] args) {
        int x = 36;
        int y = 48;
        System.out.println("The GCD of " + x + " and " + y + " is " + gcd(x, y));
    }
}

In this code, we define a static method gcd that takes two integers x and y as parameters.

The method first checks if y is zero.

If y is zero, it returns x because the GCD of x and 0 is x.

If y is not zero, the method recursively calls itself with y and the remainder of x divided by y.

In the main method, we define two integers x and y and call the gcd method with these integers.

We then print out the result.

To test this code, you can modify the values of x and y to test different inputs.

In conclusion, finding the GCD of two numbers using recursion in Java is a simple and effective way to solve the problem.

By using the Euclidean algorithm, we can break down the problem into smaller subproblems and solve them recursively.

Tags

Related Posts