Implementation of Euclid's algorithm in Python

First of all let's have a quick look at the definition of the Euclidean algorithm from Wikipedia:

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in Euclid's Elements (c. 300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use.

So, basically we can compute the GCD(A,B) of two natural numbers A and B ≠ 0 using recursion:

1. If A = 0, GCD(A,B) = B | STOP
2. If B = 0, GCD(A,B) = A | STOP
3. R := A mod B
4. GCD(A,B) = GCD(B,R)

The implementation in Python is quite easy:

def gcd(a, b):
    if a == 0:  #1
        return b

    if b == 0:  #2
        return a

    r = a % b  #3

    return gcd(b, r)  #4

That's it, but there's to mention that some more efficient algorithms for this purpose have been found.

Image