Objective

Create a recursive function to implement the Euclidean algorithm.

Difficulty

Easy

Description

Thousands of years back, an extremely ingenious method was devised to find the greatest common divisor of two integers by the great Greek mathematician, Euclid. Today, it's commonly known as the Euclidean algorithm.

The method goes as follows:

Consider two positive integers ::a:: and ::b::. Let ::r_1 = a:: and ::r_2 = b::. The greatest common divisor of ::a:: and ::b::, denoted as ::\text{gcd}(a, b)::, can likewise also be expressed as ::\text{gcd}(r_1, r_2)::.

To find ::\text{gcd}(r_1, r_2)::, we apply the rule,

::\text{gcd}(r_1, r_2) = \text{gcd}(r_2, r_3)::

where ::r_3 = r_1 \bmod r_2:: (i.e. the remainder when ::r_1:: is divided by ::r_2::).

Similarly,

::\text{gcd}(r_2, r_3) = \text{gcd}(r_3, r_4)::

where ::r_4 = r_2 \bmod r_3:: (i.e. the remainder when ::r_2:: is divided by ::r_3::).

This goes on until ::r_{i + 1}:: in ::\text{gcd}(r_i, r_{i + 1}):: becomes equal to ::0::. At that point, the greatest common divisor becomes equal to ::r_i::. That is:

::\text{gcd}(r_i, r_{i + 1}) = \text{gcd}(r_i, 0) = r_i::

Thus, the answer to the original question, of finding ::\text{gcd}(a, b)::, becomes ::r_i::.

Let's consider an example.

Suppose we want to find ::\text{gcd}(104, 16)::. Since ::104 \bmod 16 = 8::, ::\text{gcd}(104, 16) = \text{gcd}(16, 8)::. Next, since ::16 \bmod 8 = 0::, ::\text{gcd}(16, 8) = \text{gcd}(8, 0)::. And finally, ::\text{gcd}(8, 0) = 8::. Ultimately, ::\text{gcd}(104, 16) = 8::.

The best thing about the Euclidean algorithm is that each subsequent computation is smaller than the previous one. Thus, it's guaranteed that we'll eventually get to a termination point.

That exactly why Euclidean algorithm works is out of the scope of this exercise. The good news is that the proof is extremely elementary, relying on the very basic ideas from number theory and naive set theory.

Anyways, in this exercise, you have to create a function gcd() to compute the greatest common divisor of two positive integers using the aforementioned Euclidean algorithm.

You shall assume that the provided arguments are valid integers. There is no need to implement an argument-validation mechanism (though, if you want to you could).

Note that your solution MUST use recursion, NOT iteration.

View Solution

New file

Inside the directory you created for this course on JavaScript, create a new folder called Exercise-33-Euclidean-Algorithm and put the .html solution files for this exercise within it.

Solution

As stated in the description above, if the second argument to gcd(a, b) is 0, the greatest common divisor is simply a. Otherwise, the gcd is the value of gcd(a, a % b).

This is accomplished below:

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

Note that another way to accomplish the same idea above is to stop right when a % b is 0 instead of passing that 0 value to gcd().

The code below illustrates this approach:

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

The variable r is created in order to prevent repeating the expression a % b twice, first in the if conditional and then in the second return statement.