C program to find gcd of two numbers using recursion
In this post, you will learn how to find the greatest common divisor (G.C.D) or highest common factor (H.C.F) of two numbers using recursion in C programming language.
Greatest common divisor (G.C.D) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers a, b, the greatest common divisor of a and b is denoted gcd(a,b).
GCD in C using recursion
Recursion function is a function which is calling itself. The following code finds the greatest common divisor of user inputs using the recursion function. A recursion function continues until some condition is met to prevent it. That's why we use the if statement to break the infinite recursion.
/**
* C program to find GCD (HCF) of two numbers using recursion
*/
#include <stdio.h>
/* Function declaration */
int find_gcd(int a, int b);
int main()
{
int num1, num2, hcf;
/* Input two numbers from user */
printf("Enter any two numbers : ");
scanf("%d%d", &num1, &num2);
hcf = find_gcd(num1, num2);
printf("GCD of %d and %d = %d", num1, num2, hcf);
return 0;
}
/**
* Recursive function to find GCD of two numbers
*/
int find_gcd(int a, int b)
{
if(b == 0)
return a;
else
return find_gcd(b, a%b);
}
Output of the above code:
Enter any two numbers : 72 82
GCD of 72 and 82 = 2
Enter any two numbers : 90 60
GCD of 90 and 60 = 30
Enter any two numbers : 18 90
GCD of 18 and 90 = 18
Related Articles
Convert double to int JavaAverage of two numbers in C
Swapping of two numbers in C using pointers
Armstrong number in C using function
Binary to decimal C program
Sum of array elements in C
Random number generator in C
Factorial program in c using while loop
Student mark sheet program in C
C program to sort names in alphabetical order
C program to find largest number in an array
Print first 10 natural numbers using while loop in C
Simple calculator program in C
C program for simple interest
Swap two numbers without using third variable in C
Radix sort program in C
Bit stuffing program in C
Bubble sort program in C
Decimal to hexadecimal in C
Hexadecimal to decimal in C
Quick sort program in C