C Program to Find GCD of Two Numbers Using Recursion

In this example, we will use recursive functions to find the greatest common divisor (GCD), also known as the highest common factor) of two or more integers. 

The GCD is the largest positive integer that divides each of the integers. For example, the GCD of 8 and 12 is 4, and the GCD of 9 and 18 is 9.

C Program to Find GCD of Two Numbers Using Recursion

This C program takes two positive integers as input from the user and calculates GCD using recursion.

Let's create a file named gcd.c and add the following source code to it:

#include <stdio.h>
int gcd(int p, int q);

void main()
{
	int u,v,g;
	printf("Enter two numbers: ");
	scanf("%d %d",&u,&v);
	g=gcd(u,v);
	printf("Greatest Common Divisor of %d and %d is %d",u,v,g);
}

int gcd(int a, int b)
{
	int m;
	m=a%b;
	if(m==0)
		return(b);
	else
		gcd(b,m);
} 

The int gcd(int x, int y) recursive function finds the GCD of two integers, x and y, using the following three rules:

If y=0, the GCD of x and y is x.
If x mod y is 0, the GCD of x and y is y.
Otherwise, the GCD of x and y is gcd(y, (x mod y)).

To compile and run the above C program, you can use C Programs Compiler Online tool.

Output:

Enter two numbers: 8 
12
Greatest Common Divisor of 8 and 12 is 4

Comments