GCD Using Recursion in Java
Problem
The greatest common divisor of two numbers stays the same if the larger one is replaced by its remainder when divided by the smaller — repeating that replacement shrinks the pair down to the answer.
Given two integers, find their greatest common divisor using a recursive function.
Java Program
public class GCDRecursion {
static int gcd(int a, int b) {
if (b == 0) return a; // b has shrunk to zero — a is the answer
return gcd(b, a % b);
}
public static void main(String[] args) {
int a = 48, b = 18;
System.out.println("GCD: " + gcd(a, b));
}
}Output
Core Logic
Calling the function again on the smaller number and the remainder, instead of looping, shrinks the pair toward the answer one recursive call at a time.
- 1The base case
if (b == 0) return a;fires once the second argument reaches zero, at which pointaalready holds the answer. - 2Every other call returns
gcd(b, a % b), replacing the pair with the smaller value and the remainder of dividing the two. - 3Each call's remainder is always smaller than the previous smaller value, so the pair shrinks quickly toward the base case.
- 4No loop counter or running variable is needed — each call's return value is simply passed straight back up unchanged.
48 and 18: gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0), and the base case returns 6.Key Point: Each call does no work of its own beyond computing the next pair — the entire answer comes from whichever call happens to hit the base case.
Why: Each call shrinks the pair at a rate related to the Fibonacci sequence in reverse, so both the number of calls and the stack frames they leave behind grow logarithmically with the smaller number.