Recursive Program to Find Gcd of Two Numbers

Introduction and General Idea:

Gcd stands for Greatest common divisor and is the name suggest is the largest number that can divide both the numbers.
1) Gcd of 5 and 0: It is evident that 5 is the largest number that can divide 5 and 0.
2) Gcd of 0 and 5: Similar to the above example, 5 can divide both the numbers.
So, from example 1 and 2, we can see that if one of the numbers is 0, the other number is the gcd.

3) Gcd of 20 and 5: The greatest number that can divide both 20 and 5 is 5 itself. But how do we get there? We place the second-placed number in the first and then find the remainder of the first and second place number and place it in second place. This process is done until one of the numbers becomes 0 and we can use the concept from example 1 and example 2.
gcd(20,5)
=gcd(5,20%5)
=gcd(5,0)=5 is the gcd

Pseudocode:

Let x and y be the two numbers whose gcd is to be calculated, then

gcd(int x,int y)
{
	if(x==0)
	{
		return(y);
	}
	
	else if(y==0)
	{
		return(x);
	}
	
	else
	{
		return(gcd(y,xmody));
	}
}

Code in C:

#include<stdio.h>
#include<conio.h>

int gcd(int,int);

int main()
{
	int a;
	int b;
	int g; /*to store the gcd */
	
	printf("Enter two numbers to know their gcd: ");
	scanf("%d%d",&a,&b);
	g=gcd(a,b);
	
	printf("\nThe gcd of two numbers %d and %d is: %d",a,b,g);
	getch();
	return(0);
}



int gcd(int x,int y)
{
	if(x==0)
	{
		return(y);
	}
	
	else if(y==0)
	{
		return(x);
	}
	
	else
	{
		return(gcd(y,x%y));
	}
}

Output:

Recursive Program to Find Gcd of Two Numbers

Feel free to comment down below if you are confused in any steps.

Also Read: C Program to Generate Random Number Using Middle-Square Method

LEAVE A REPLY

Please enter your comment!
Please enter your name here