Greatest Common Divisor using the Euclidean Algorithm
Below is an example of how to create the recursive function of computing the greatest common divisor 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?
