Create a recursive function to implement the Euclidean algorithm.




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::).


::\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.