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

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).

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

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.

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.

void recurse()

{

... .. ...

recurse();

... .. ...

}

int main()

{

... .. ...

recurse();

... .. ...

}

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;

` ````
#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