 ### Program 314: GCD of a number using Recursion

Program 314: GCD of a number using Recursion

```#include<stdio.h>
int GetGCD(int temp1,int temp2);
main()
{
int num1,num2,gcd,lcm,x;
printf("Enter number 1 and number 2\n");
scanf("%d%d",&num1,&num2);
gcd=GetGCD(num1,num2);
lcm=(num1*num2)/gcd;
printf("gcd is %d\n",gcd);
printf("Lcm is %d\n",lcm);
}

int GetGCD(int temp1,int temp2)
{
if(temp2!=0)
{
GetGCD(temp2,temp1%temp2);
}
else
{
return(temp1);
}
}```
Explanation:

1. This program starts with initializing :
• num1,num2→ To store numbers
• gcd,lcm →Used to store gcd and lcm
• int GetGCD→ recursive function
2. ` printf("Enter number 1 and number 2\n");`
`scanf("%d%d",&num1,&num2);`
To take input from user
3. `gcd=GetGCD(num1,num2);`
Calling GetGCD Function and received output from the called function(i.e GetGCD will be sored in gcd
4. ```int GetGCD(int temp1,int temp2)
{
if(temp2!=0)
{
GetGCD(temp2,temp1%temp2);
}
else
{
return(temp1);
}
}```
Now lets take numbers 20,30 and passed it ti GetGCD so now temp1=20,temp2=30
now temp2=30!=0 is true so if part is executed
5. Now
1. `GetGCD(temp2,temp1%temp2);--->GetGCD(30,20%30)-->GetGCD(30,20)`
2. Now again GetGCD function is called.But now temp1=30,temp2=20
3. Now again
4. ```if(temp2!=0)
{
GetGCD(temp2,temp1%temp2);
}
else
{
return(temp1);
}```
5. Since temp2=20 and is not equal to zero which is true and if part is executed
6. So GetGCD(20,30%20)--->GetGCD(20,10)
7. Now in next recursion temp1=20,temp2=10
8. Since temp2=10 and is not equal to zero which is true and if part is executed
9. So GetGCD(10,20%10)--->GetGCD(10,0).Now temp1=10,temp2=0
10. Since temp2=0 and is equal to zero which is true so else part is executed
11. ```return(temp1);--->
Finally temp1 which is 10 will be returned and stored in gcd```
6. ```gcd=GetGCD(num1,num2);
lcm=(num1*num2)/gcd;
printf("gcd is %d\n",gcd);
printf("Lcm is %d\n",lcm);```
so here gcd=10.
7. lcm=(num1*num2)/gcd-->(20*30)/10=600/10=60
8. So gcd=10 and lcm=60

Output: 