Write a C++ Program to Find G.C.D Using Recursion

Finding the greatest common divisor (GCD) of two numbers using recursion is a popular algorithmic problem.

In this tutorial, we will see how to implement this algorithm in C++.

First, let’s understand what GCD is. GCD is the largest positive integer that divides both numbers without leaving a remainder.

For example, the GCD of 8 and 12 is 4, because 4 divides both 8 and 12 without leaving a remainder.

The basic idea behind the recursive algorithm to find GCD is that, if a and b are the two numbers, then the GCD of a and b is the same as the GCD of b and the remainder of a divided by b. In other words, we can write the following recursive function:

int gcd(int a, int b)
{
    if (b == 0) {
        return a;
    }
    return gcd(b, a %% b);
}

This function takes two integers, a and b, as its input parameters. If b is zero, then the GCD of a and b is a itself.

Otherwise, we call the same function recursively with b as the first parameter and the remainder of a divided by b as the second parameter.

Let’s see how this function works with an example. Suppose we want to find the GCD of 24 and 16. We can call the gcd function as follows:

int result = gcd(24, 16);

On the first call, a is 24 and b is 16. Since b is not zero, we call the same function again with b as the first parameter and the remainder of 24 divided by 16 (which is 8) as the second parameter.

On the second call, a is 16 and b is 8. Again, b is not zero, so we call the same function again with b as the first parameter and the remainder of 16 divided by 8 (which is 0) as the second parameter.

On the third call, b is 0, so the function returns a, which is 8. Therefore, the GCD of 24 and 16 is 8.

To summarize, the recursive algorithm to find GCD is a simple and elegant solution that can be implemented in just a few lines of code.