The greatest common divisor (often abbreviated to gcd) of two nonnegative integers is the largest integer that divides evenly into both. In the third century BCE, the Greek mathematician Euclid...

The greatest common divisor (often abbreviated to gcd) of two nonnegative integers is the largest integer that divides evenly into both. In the third century BCE, the Greek mathematician Euclid discovered that the greatest common divisor of x and y can always be computed as follows:

 • If x is evenly divisible by y, then y is the greatest common divisor.

• Otherwise, the greatest common divisor of x and y is always equal to the greatest common divisor of y and the remainder of x divided by y. Use Euclid’s insight to write a recursive function gcd (x, y) that computes the greatest common divisor of x and y.