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

What is HCF/GCD?

HCF or the Highest Common Factor is defined as the highest number which can able to divide all the numbers perfectly. The highest common factor (HCF) is also called the greatest common divisor (GCD).

HCF by Division Method

In this program, we are using the Division method to find the HCF or GCD using the below steps

• 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 division till the remainder reaches zero and then take the last divisor as the HCF or GCD.

Recursion in C++

Recursion can be defined as a function that calls itself repeatedly until a condition is met. 

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

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. Then pass the entered number to the HCF function. In this function, check the condition n2 != 0 using an if conditional statement. then, 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;
 

                                          #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;
}
                                      

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