Java Program to Find GCD Using Recursion

You can find the GCD of two numbers in Java using recursion with the method gcd(int a, int b) that returns b == 0 ? a : gcd(b, a % b).

Examples

Input48, 18

Output6

Input100, 25

Output25

Input7, 3

Output1

How to Think About It

To find the GCD using recursion, think about the fact that the GCD of two numbers also divides their difference. We use the rule that GCD(a, b) equals GCD(b, a % b) until the second number becomes zero. When it is zero, the first number is the GCD.

Algorithm

1

Get two numbers as input.

2

Check if the second number is zero.

3

If yes, return the first number as the GCD.

4

If no, call the function again with the second number and the remainder of the first number divided by the second.

5

Repeat until the second number becomes zero.

Code

java

public class GCD {
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

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

Output

GCD of 48 and 18 is 6

Dry Run

Let's trace gcd(48, 18) through the code

1

Initial call

gcd(48, 18) checks if 18 == 0 (false), calls gcd(18, 48 % 18)

2

Second call

gcd(18, 12) checks if 12 == 0 (false), calls gcd(12, 18 % 12)

3

Third call

gcd(12, 6) checks if 6 == 0 (false), calls gcd(6, 12 % 6)

4

Fourth call

gcd(6, 0) checks if 0 == 0 (true), returns 6

5

Return values

Each call returns 6 back up the chain

Call	a	b	a % b	Return
1	48	18	12	gcd(18, 12)
2	18	12	6	gcd(12, 6)
3	12	6	0	gcd(6, 0)
4	6	0	-	6

Why This Works

Step 1: Base case

When the second number b becomes zero, the first number a is the GCD, so the recursion stops.

Step 2: Recursive call

If b is not zero, the function calls itself with b and the remainder of a % b, reducing the problem size.

Step 3: Mathematical property

This works because the GCD of two numbers also divides their remainder, so the problem simplifies each time.

Alternative Approaches

Iterative approach

java

public class GCD {
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

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

This uses a loop instead of recursion, which can be more efficient for large inputs by avoiding stack overhead.

Using Euclid's subtraction method

java

public class GCD {
    public static int gcd(int a, int b) {
        if (a == b) {
            return a;
        }
        if (a > b) {
            return gcd(a - b, b);
        } else {
            return gcd(a, b - a);
        }
    }

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

This method uses subtraction instead of modulus but can be slower for large numbers.

Complexity: O(log(min(a, b))) time, O(log(min(a, b))) space

Time Complexity

Each recursive call reduces the problem size roughly by the remainder, so the number of calls is proportional to the logarithm of the smaller number.

Space Complexity

The recursion stack grows with each call, so space used is proportional to the number of recursive calls, which is O(log(min(a, b))).

Which Approach is Fastest?

The iterative approach avoids recursion overhead and uses constant space, making it faster and more memory efficient for large inputs.

Approach	Time	Space	Best For
Recursive (modulus)	O(log(min(a,b)))	O(log(min(a,b)))	Simple code, small inputs
Iterative (modulus)	O(log(min(a,b)))	O(1)	Large inputs, performance
Recursive (subtraction)	O(min(a,b))	O(min(a,b))	Educational, simple math