## C program to find LCM and GCD using recursion

C program to find LCM and GCD using recursion of two integers entered by the user.

Please go through following C programming articles to understand the concept of the program.

We have use following formula to find the LCM of two numbers using GCD

`LCM = (number1 * number2) / GCD`

## C program to find GCD and LCM using recursion

``````#include <stdio.h>
int gcd(int x, int y);  //function prototype

int main()
{
int num1, num2, hcf, lcm;

printf("Enter two integer Values:\n");
scanf("%d %d", &num1, &num2);

hcf = gcd(num1, num2);
printf("GCD: %d", hcf);
printf("\nLCM: %d", (num1 * num2) / hcf);
return 0;
}
//recursive function
int gcd(int x, int y)
{
if (y == 0)   //recursion termination condition
{
return x;
}
else
{
return gcd(y, x % y);   //calls itself
}
}
``````

In the above program, recursive function `gcd` returns the value of gcd. The termination condition of the recursive function is `y == 0` which checks whether the number is equal to zero or not.