Recursion for Coding Interviews in Java/

...

/

Solution Review: Find the Greatest Common Divisor

Solution Review: Find the Greatest Common Divisor

This lesson provides a detailed review of the solution to the challenge of the previous lesson.

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. ...