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: