Java Code Example: Greatest Common Divisor (GCD)

The Greatest Common Divisor (GCD) of two numbers is the largest number that divides both numbers without leaving a remainder. For example, the GCD of 48 and 18 is 6 because 6 is the largest number that divides both evenly.

One of the most efficient ways to compute the GCD is using recursion, specifically Euclid’s Algorithm:

1. If b == 0, then GCD(a, b) = a (base case).
2. Otherwise, GCD(a, b) = GCD(b, a % b) (recursive case).

This algorithm repeatedly reduces the problem size until reaching the base case.

Java Code Example

public class GCDRecursion {
    // Recursive method to find GCD using Euclidean Algorithm
    public static int findGCD(int a, int b) {
        if (b == 0) {
            return a;  // Base case: when the second number becomes zero
        }
        return findGCD(b, a % b);  // Recursive case: call GCD with (b, remainder of a/b)
    }

    public static void main(String[] args) {
        int num1 = 48, num2 = 18;
        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + findGCD(num1, num2));
    }
}

Output

GCD of 48 and 18 is: 6

Explanation

1. Base Case:
   • If b == 0, return a as the GCD.
2. Recursive Case:
   • Compute a % b to get the remainder.
   • Call findGCD(b, a % b), reducing the problem size with each call.

Example Breakdown (GCD of 48 and 18)

findGCD(48, 18) →  findGCD(18, 48 % 18) →  findGCD(18, 12)
findGCD(18, 12) →  findGCD(12, 18 % 12) →  findGCD(12, 6)
findGCD(12, 6)  →  findGCD(6, 12 % 6)  →  findGCD(6, 0)
findGCD(6, 0)   →  Return 6 (Base case reached)

Key Takeaways

✅ Efficient Approach – Euclidean Algorithm runs in O(log(min(a, b))) time.
✅ Recursive Simplicity – Reduces problem size at each step until base case.
✅ Real-World Usage – Common in number theory, cryptography, and computing least common multiples (LCM).