Java Recursive Method: Find the greatest common divisor

Java Recursive: Exercise-7 with Solution

Recursive GCD of Two Numbers

Write a Java recursive method to find the greatest common divisor (GCD) of two numbers.

Sample Solution:

Java Code:

public class GCDCalculator {

  public static int calculateGCD(int num1, int num2) {
    // Base case: if the second number is 0, the GCD is the first number
    if (num2 == 0) {
      return num1;
    }

    // Recursive case: calculate the GCD by recursively calling the method with num2 as the new num1 and the remainder as num2
    int remainder = num1 % num2;
    return calculateGCD(num2, remainder);
  }

  public static void main(String[] args) {
    int number1 = 16;
    int number2 = 18;
    int gcd = calculateGCD(number1, number2);
    System.out.println("The GCD of " + number1 + " and " + number2 + " is: " + gcd);
  }
}

Sample Output:

The GCD of 16 and 18 is: 2

Explanation:

In the above exercises -

First, we define a class GCDCalculator that includes a recursive method calculateGCD() to find the greatest common divisor (GCD) of two numbers.

The calculateGCD() method follows the recursive GCD definition. It has two cases:

1. Base case: If the second number (num2) is 0, the GCD is the first number (num1). This is because any number divided by 0 is the number itself.
2. Recursive case: For any two numbers (num1 and num2), we calculate the remainder when num1 is divided by num2. We then recursively call the method with num2 as the new num1 and the remainder as num2. This process continues until num2 reaches 0.

In the main() method, we demonstrate the calculateGCD() method by finding the GCD of two numbers (16 and 18) and printing the result.

Flowchart:

Java Code Editor:

Java Recursive Previous: Reverse a given string.
Java Recursive Next: Count occurrences of a specific element.