Search⌘ K
Home
Courses
Recursion for Coding Interviews in JavaScript

Solution Review: Find the Greatest Common Divisor

Explore how to implement and understand a recursive approach to find the greatest common divisor (GCD) of two numbers. This lesson guides you through the algorithm that reduces the problem by repeatedly subtracting smaller values until both numbers are equal, revealing the GCD. By the end, you will grasp the recursive logic and see step-by-step examples that illustrate the process clearly.

We'll cover the following...

Solution: Using Recursion

Javascript (babel-node)
function gcd(testVariable1, testVariable2) {
  // Base case
  if (testVariable1 == testVariable2) {
    return testVariable1;
  }
  // Recursive case
  if (testVariable1 > testVariable2) {
    return gcd(testVariable1 - testVariable2, testVariable2);
  }
  else {
    return gcd(testVariable1, testVariable2 - testVariable1);
  }
}
// Driver Code
var number1 = 6;
var number2 = 9;
console.log(gcd(number1, number2));

Explanation

The naive approach to finding GCDGCD of 22 numbers is to list all their divisors. Then pick the common divisors, and then select the greatest out of them.

However, an easy mathematical simplification can make our task easier.

The idea behind calculating GCDGCD is: If m>nm>n, GCD(m,n)GCD(m,n) is the same as GCD(m−n,n)GCD(m-n,n).

This is because if m/dm/d and n/dn/d both leave no remainder, then (m−n)/d(m-n)/d leaves no remainder, either.

This leads to the following algorithm:

gcd(m,n)={m                          ...