## Greatest Common Divisor using the Euclidean Algorithm

Below is an example of how to create the recursive function of computing the

**greatest common diviso**r using the Euclidean Algorithm.

* This tutorial assumes you understand the following.

## Euclid’s Algorithm

When studying computer science a famous algorithm taught to students is the Euclidean Algorithm which is used to compute the greatest common divisor of two integers. It’s definition is below.

[pmath] gcd(x,y) [/pmath]

## Computing various examples

So how does it work? Well, let’s follow the definition, but before doing that, do you remember how to compute the remainder of two integers in c++? If you don’t, well it’s the

**%**(mod) operator.

1 2 3 4 5 6 7 8 9 10 11 | // Computing the gcd of 45 and 9 // gcd(45, 9) = gcd(9, 45 % 9 ) = gcd(9, 0) = 9 // Computing the gcd of 54 and 12 // gcd(54, 12) = gcd(12, 54 % 12) = gcc(12, 6) = gcd(6, 12 % 6) = gcd(6, 0) = 6 |

Now that you saw how this works, try creating the recursive function for the greatest common divisor by simply using the definition. **[Hint: Treat the Conditions as your base cases]**

## Recursive function of Greatest Common Divisor

The solution for the function is below. If you notice you’ll see that the definition was simply translated into a recursive c++ function aside from an additional base case that handles erroneous input.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 | int gcd(int x, int y) { // Condition 1 // if ( y == 0 ) return x; // Condition 2 // else if ( x >= y && y > 0 ) return gcd(y, x%y); // If not condition was met return error // else return -1; } |

## Going further

- Can you figure a way to make sure x is always the larger value?
**[Hint: C++ Helper Functions]** - Can you write the iterative version?