GCD in C++ - How to Calculate the Greatest Common Divisor

Let's learn how to calculate the GCD of a number, its greatest common divisor, using C++ recursion. First, let's understand what GCD is.

What is GCD ?

Every natural number can be divided by others, resulting in natural numbers.
For example, 8 can be divided by:
8/1 = 8
8/2 = 4
8/4 = 2
8/8 = 1

11, which is a prime, can be divided by:
11/1 = 11
11/11 = 1

Every natural number has at least two dividers: 1 and itself.
So any two natural numbers always have some divisor in common, even if it's just 1.

That's where GCD comes in, the maximum, we want to calculate the greatest common divisor, the greatest divisor of these two numbers.

How to calculate GCD

Let's calculate the dividers of 18:
18/1 = 18
18/2 = 9
18/3 = 6
18/6 = 3
18/9 = 2
18/18 = 1

Now the 15 dividers:
15/1 = 15
15/3 = 5
15/5 = 3
15/15 = 1

1 and 3 are the repeating numbers, the common dividers. And which one is the biggest?
Pimba, it's the 3!

How to calculate GCD with C++ and recursion

What we are going to do is simple ... let's take the largest number and calculate the rest of the division by the smallest.
If it gives 0, it's over, the lowest is the GCD.

If it doesn't give 0, we continue with some more calculations until the rest of the division of the first by the second is 0, but we get two things: the smallest number and the rest of the division of the largest by the smallest.

So we do the recursion, now passing as arguments the smallest number and the rest of the division of the largest by the smallest.

Our code looks like this:

#include <iostream>
using namespace std;

int mdc(int num1, int num2)
{
    if(num1%num2 == 0)
        return num2;
    else
        return mdc(num2, num1%num2);
}

int main()
{
    int num1, num2;

    cout<<"Numbers (largest and smallest): ";
    cin>> num1 >> num2;

    cout<<"GCD: "<<mdc(num1, num2)<<endl;
}

To understand mathematically the previous logic, you must study Euclid's Algorithm.