GCD (Greatest Common Divisor) of 2 numbers using Recursion C program

This program displays the GCD ( Greatest Common Divisor) of 2 numbers using Recursion. This is a part of Mumbai University MCA Colleges C Program MCA

#include<stdio.h>

#include<conio.h>

void main()

{

           int gcd(int num1,int num2,int n);

           int num2,num1,n,ans;

           clrscr();

           printf("\n Enter two numbers");

           scanf("%d %d",&num1,&num2);

           if(num1> num2)                         /* select the limit for the divisor */

                    n=num1/2;

           else

                    n=num2/2;

           ans=gcd(num1,num2,n);

           printf("GCD of %d and %d is %d",num1,num2,ans);

           getch();

}

int gcd(int num1,int num2,int n)

{

     if(n==1)                      /*if divisor is 1 */

           return(1);

    else

    {                                   /* find if n divides both the numbers */

         if(num1%n==0 && num2%n==0)

                return(n);

        else                            /*check the numbers with next values */

                 gcd(num1,num2,(n-1));

  }

}

OUTPUT:

Enter two numbers           36         45

GCD of 36 and 45 is 9

Hope this Program is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.