Search⌘ K
Home
Courses
Recursion for Coding Interviews in Java

Solution Review: Find the Greatest Common Divisor

Understand how to solve for the greatest common divisor using recursion in Java. Explore the recursive method's base and recursive cases, see how the algorithm works with examples, and learn to trace recursion using the stack.

We'll cover the following...

Solution: Greatest Common Divisor

Java
class Solution {
    
    public static int gcd(int num1, int num2) {
        // Computing absolute value
        num1 = Math.abs(num1);
        num2 = Math.abs(num2);
        // Base case
        if (num1 == 0) {
            return num2;
        }
        else if (num2 == 0) {
            return num1;
        }
        // Recursive case
        if (num1 > num2) {
            return gcd(num1 % num2, num2);
        }
        else {
            return gcd(num1, num2 % num1);
        }
    }
    public static void main( String args[] ) {
        int x = 56;
        int y = 42;
        int result = gcd(x, y);
        System.out.println("The GCD of " + x + " and " + y + " is:");
        System.out.println(result);
    }
}

Understanding the Code

In the code above, the method gcd is recursive, since it makes a recursive call in the method body. Below is an explanation of the code above.

Driver Method

  • In the main() code, we have defined three integer variables: x, y and result.

  • The variable result, stores the greatest common divisor of x and y, returned by the gcd method.

  • Line 31 prints result.

Recursive Method

  • The return type of this method is an integer because GCD of two integers is always an integer.

  • The method takes two integer input arguments num1 and num2. ...