# HCF program using Recursion.

## HCF program using Recursion.

The greatest number which divides each of the two or more numbers is called HCF or Highest Common Factor. It is also called the Greatest Common Measure(GCM) and Greatest Common Divisor(GCD). In this post we will see hcf program in C/C++ using recursion.

Also Check : Program to find GCD and LCM of two numbers.

Q. Write a program in C and C++ to evaluate HCf of the given numbers using recursion.

## 1. Program

C Code :

``````//calculate H.C.F. using recursion
#include<stdio.h>

int hcf(int, int);

int main()
{
int n1,n2;
printf("\n Enter two positive integers:");
scanf("%d%d",&n1, &n2);

printf("\n H.C.F. of %d & %d is : %d", n1, n2, hcf(n1,n2));

return 0;
}

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

C++ Code :

``````//calculate H.C.F. using recursion
#include<iostream>

using namespace std;

int hcf(int, int);

int main()
{
int n1,n2;
cout<<"\n Enter two positive integers:";
cin>>n1>>n2;
cout<<"\n 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;
}``````

## 3. Program Parts :

1. #include is a pre-processor directive. It is used to include header files.
2. stdio/iostream is header file which has certain commands that c/c++ supports. E.g. return, main, etc.
3. .h is an extension for header file.
4. hcf(int n1, int n2) is a function name.
5. int is data type. It indicates that the program returns a value.
6. main() is main function that indicates the compiler that the user written programs starts from here.
7. print/cout is the keyword use to print a message.
8. scanf/cin is the keyword use to store values in variables.
9. return statement is use to return a value. If any error occurs the program will return 0.

## 4. Explanation :

Compiler checks all the necessary header files that we require to execute our C C++ program. Once files are checked compiler goes to next step. Here we have declared our function ‘hcf‘ which takes teo arguments of integer data type. Then in next step compiler enters main function. Here we ask user to enter two numbers. Then in print statement we call our function hcf. As soon compiler encounters hcf function it jumps to its definition.

Here we check if value of n2 is not equal to zero. If it is equal to zero then compiler executes else part of the statement. If not then the function calls itself (recursion). But here the arguments that we are passing are different from the earlier arguments. Here in place of n1 we give n2 as first argument. And in place n2 we give remainder of n1 divided by n2. This is different method of finding hcf. This step continues till the second argument becomes 0. Finally when the condition is false compiler returns to the main function with the hcf value. It prints the value and the program execution terminates.

### Conclusion.

So this was the program to calculate hcf of a program in C/C++ using recursion. Hope you like it. And yes as we used different logic here you can also use your logic. Do tell us what other way you can think to calculate hcf of given numbers using recursion. If you found this useful then do share it with your friends and programming buddies.