JavaScript Program to Find GCD Using Recursion

You can find the GCD of two numbers in JavaScript using recursion with the function function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); } which calls itself until the remainder is zero.

Examples

Inputgcd(48, 18)

Output6

Inputgcd(101, 10)

Output1

Inputgcd(0, 5)

Output5

How to Think About It

To find the GCD using recursion, think of the Euclidean algorithm: if one number divides the other exactly, that divisor is the GCD. Otherwise, replace the larger number with the remainder of dividing the larger by the smaller, and repeat the process until the remainder is zero.

Algorithm

1

Take 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

javascript

function gcd(a, b) {
  if (b === 0) {
    return a;
  }
  return gcd(b, a % b);
}

console.log(gcd(48, 18));

Output

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 previous call returns 6 up the stack, final output is 6

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

The function stops calling itself when the second number b becomes zero, returning the first number a as the GCD.

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: Euclidean algorithm

This process uses the Euclidean algorithm, which guarantees the GCD is found by repeated remainder calculations.

Alternative Approaches

Iterative approach

javascript

function gcdIterative(a, b) {
  while (b !== 0) {
    let temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}
console.log(gcdIterative(48, 18));

Uses a loop instead of recursion, which can be easier to understand for some and avoids call stack overhead.

Using subtraction (recursive)

javascript

function gcdSubtraction(a, b) {
  if (a === b) return a;
  if (a > b) return gcdSubtraction(a - b, b);
  return gcdSubtraction(a, b - a);
}
console.log(gcdSubtraction(48, 18));

Uses repeated subtraction instead of modulo, which is less efficient but conceptually simple.

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

Time Complexity

The Euclidean algorithm reduces the problem size roughly by half each step, so it runs in logarithmic time relative to the smaller input.

Space Complexity

Recursive calls add to the call stack, so space complexity is also logarithmic in the smaller input.

Which Approach is Fastest?

The modulo recursion is faster and uses fewer steps than subtraction recursion; iterative avoids recursion overhead but has similar time complexity.

Approach	Time	Space	Best For
Recursive modulo	O(log(min(a,b)))	O(log(min(a,b)))	Clear recursive logic
Iterative modulo	O(log(min(a,b)))	O(1)	Memory efficient, avoids recursion
Recursive subtraction	O(min(a,b))	O(min(a,b))	Simple concept, less efficient