Finding the greatest common divisor using recursion

In this recipe, we will use recursive functions to find the greatest common divisor (GCD), also known as the highest common factor) of two or more integers. The GCD is the largest positive integer that divides each of the integers. For example, the GCD of 8 and 12 is 4, and the GCD of 9 and 18 is 9.

How to do it…

The int gcd(int x, int y) recursive function finds the GCD of two integers, x and y, using the following three rules:

• If y=0, the GCD of x and y is x.
• If x mod y is 0, the GCD of x and y is y.
• Otherwise, the GCD of x and y is gcd(y, (x mod y)).

Follow the given steps to find the GCD of two integers recursively:

1. You will be prompted to enter two...