C program to find gcd of given two numbers using recursion

In this article we will learn to implement a C program to find gcd of given two numbers using recursion. A C program is provided below to read two numbers and find their GCD.

Program is as follows:

/*
 * C program to find GCD of given two integers using recursive and non-recursive functions
 * Author: P.S.SuryaTeja
*/
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <stdlib.h>

int gcd(int num1, int num2)
{
	int i, hcf;
	if(num1 < num2)
	{
		for(i = 1; i <= num1; i++)
		{
			if((num1 % i == 0) && (num2 % i == 0))
				hcf = i;
		}
	}
	else
	{
		for(i = 1; i <= num2; i++)
		{
			if((num1 % i == 0) && (num2 % i == 0))
				hcf = i;
		}
	}
	return hcf;
}

int rgcd(int num1, int num2)
{
	while(num1 != num2)
	{
		if(num1 > num2)
			return rgcd(num1 - num2, num2);
		else
			return rgcd(num1, num2 - num1);
	}
	return num1;
}

int main(int argc, char **argv)
{
	int num1, num2;
	printf("Enter two numbers: ");
	scanf("%d%d", &num1, &num2);
	printf("\nGCD of %d and %d using non-recursion is: %d", num1, num2, gcd(num1, num2));
	printf("\nGCD of %d and %d using recursion is: %d", num1, num2, rgcd(num1, num2));
    getch();
    return 0;
}

Input and output for the above program is as follows:

Enter two numbers: 24 6

GCD of 24 and 6 using non-recursion is: 6
GCD of 24 and 6 using recursion is: 6

Suryateja Pericherla

Suryateja Pericherla, at present is a Research Scholar (full-time Ph.D.) in the Dept. of Computer Science & Systems Engineering at Andhra University, Visakhapatnam. Previously worked as an Associate Professor in the Dept. of CSE at Vishnu Institute of Technology, India.

He has 11+ years of teaching experience and is an individual researcher whose research interests are Cloud Computing, Internet of Things, Computer Security, Network Security and Blockchain.

He is a member of professional societies like IEEE, ACM, CSI and ISCA. He published several research papers which are indexed by SCIE, WoS, Scopus, Springer and others.