C++ Recursion – Greatest Common Divisor

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


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

Tags: , , , , , ,

  • WithOutModOperator

    int gcd(int m, int n)
    {
        if (m>n)
        {
            if((m-n) == 0) return m;
            return gcd(n,m-n);
        }
        else
        {
            if((n-m) == 0) return n;
            return gcd(m, n-m);
        }
    }

    • Chrischeung0101

      can somebody expain to me why this will work out the solution?

      my teacher just give me a quiz exactily like this.