Contact Learn C
Copy Program Share Program

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:
GCD of a number using Recursion



Download App and Learn when ever you want

Get it on PlayStore
Get it on Amazon App Store
Get it on Aptoide