/*This program finds out the GCD of two numbers with and without using recursion.
The method using recursion for finding the GCD was given by EUCLID and one can read more about EULICD's algorithm.
*/
#include<stdio.h>
#include<conio.h>
int num1,num2;
int Recursiveapproach(int copy1,int copy2);//recursive function which return the GCD of two numbers
void NonRecursiveapproach(int copy1,int copy2);//non recursive function
int main()
{
    int gcd;
    printf("This programs demonstrate GCD calculation using recursive and non-recursive approach\n");
    printf("\nEnter first number\n");
    scanf("%d",&num1);
    printf("\nEnter second number\n");
    scanf("%d",&num2);
    if(num1>num2)//Our first parameter is the larger of the two numbers
    gcd=Recursiveapproach(num1,num2);
    else
    gcd=Recursiveapproach(num2,num1);
    printf("The GCD calculated using recursive approach is %d\n",gcd);
    NonRecursiveapproach(num1,num2);
    getch();
    return 0;
}
int Recursiveapproach(int copy1,int copy2)
{/*In the recursive method the larger number is divided by the smaller number ,the remainder is checked and then another call is made with
paramters as smaller number and the remainder*/
    if(copy2==0)//when the rmainder passed is zero than we have GCD as the smaller number passed(wiz copy1)
        return copy1;
    else
        Recursiveapproach(copy2,copy1%copy2);
}
void NonRecursiveapproach(int copy1,int copy2)
{
int div=2;//We divide both the numbers with div. We use the prime factorisation method.
int gcd=1;//Initialise the GCD as 1
while(!(copy1==1||copy2==1||div>copy1||div>copy2))
{
if((copy1%div==0)&&(copy2%div==0))
{//If both the numbers are divisible by div then divide and multiply div to the gcd
gcd=gcd*div;
copy1=copy1/div;
copy2=copy2/div;
}
else//Otherwise divide the number which is divisible by div
if((copy1%div==0)&&(copy2%div!=0))
copy1=copy1/div;
else
if((copy1%div!=0)&&(copy2%div==0))
copy2=copy2/div;
else
if((copy1%div!=0)&&(copy2%div!=0))
div++;//else increment div
}
printf("The GCD calculated without using recursion is %d",gcd);
}
/*A sample run of the program was carried out and the results were found as:-
This programs demonstrate GCD calculation using recursive and non-recursive approach
Enter first number
45
Enter second number
36
The GCD calculated using recursive approach is 9
The GCD calculated without using recursion is 9
*/