C++ Program to find the G.C.D using recursion

This program is an example to find the GCD of two positive integers (entered by the user) using recursion in C++ programming.

What is HCF/GCD?

The Highest Common Factor (HCF) of two numbers is the highest possible number that divides both the numbers completely. The highest common factor (HCF) is also called the greatest common divisor (GCD).

How can we calculate HCF?

There are many ways to find the highest common factor of the given numbers. Irrespective of the method, the answer to the HCF of the numbers would always be the same. There are 3 methods to calculate the HCF of two numbers:
•    HCF by listing factors method
•    HCF by prime factorization
•    HCF by division method

HCF by Division Method

The HCF of two numbers can be calculated using the division method.
•    Step 1: Divide the larger number by the smaller number and check the remainder.
•    Step 2: Then, make the remainder of the previous step the new divisor and the divisor of the previous step as the new dividend and perform the long division again.
•    Step 3: continue the long division process till we get the remainder as 0. It should be noted that the last divisor will be the HCF of those two numbers.

Recursion in C++

A function that calls itself is known as a recursive function. And, this technique is known as recursion.
The recursion continues until some condition is met.
To prevent infinite recursion, the if...else statement (or similar approach) can be used where one branch makes the recursive call and the other doesn't.

Working on Recursion in C++

void recurse()
{
    ... .. ...
    recurse();
    ... .. ...
}
int main()
{
    ... .. ...
    recurse();
    ... .. ...
}
 

How do implement a C++ program to find HCF?

Here the program takes two positive integers from the user to calculate the G.C.D using recursion. 
Ask the user to enter two positive integers and read the number to the variables n1 and n2. Define a recursive function HCF ( ) to find the G.C.D of the number.
Pass the entered number to the HCF function.
int hcf(int n1, int n2)
in this function, check the condition n2 != 0 in an if conditional statement.
if (n2 != 0)
perform the operation recursively by calling the function with arguments n2, n1 % n2 and return the value .
return hcf(n2, n1 % n2);
else return the value n1 to the main function.
return n1;


Algorithm

Step 1:  Call the header file iostream.

Step 2: Use the namespace std.

Step 3: Define a function HCF ( );
              if (n2 != 0)
              return hcf(n2, n1 % n2);
              else 
              return n1

Step 4: Open the integer type main function; int main().

Step 5: Declare integer variables; n1 and n2;

Step 6: Print a message to enter two positive integers;

Step 7: Read the value into the variables n1 and n2;

Step 8: Call the function HCF(int n1, int n2);

Step 9: Exit;
 

C++ Source Code

                                          #include <iostream>
using namespace std;

int hcf(int n1, int n2);

int main()
{
   int n1, n2;

   cout << "Enter two positive integers: ";
   cin >> n1 >> n2;

   cout << "H.C.F of " << n1 << " & " <<  n2 << " is: " << hcf(n1, n2);

   return 0;
}

int HCF(int n1, int n2)
{
    if (n2 != 0)
       return HCF(n2, n1 % n2);
    else 
       return n1;
}
                                      

OUTPUT

Enter two positive integers: 8
12
H.C.F of 8 & 12 is: 4