40.C Program to Find G.C.D Using Recursion

C Program to Find G.C.D Using Recursion

Example to find the GCD of two positive integers (entered by the user) using recursion in C programming.

To understand this example, you should have the knowledge of following C programming topics:

• C Programming Functions
• C Programming User-defined functions
• C Programming Recursion

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

Visit this page to learn how you can calculate the GCD using loops.

Example: GCD of Two Numbers using Recursion

#include <stdio.h>
int hcf(int n1, int n2);
int main()
{
   int n1, n2;
   printf("Enter two positive integers: ");
   scanf("%d %d", &n1, &n2);

   printf("G.C.D of %d and %d is %d.", n1, n2, hcf(n1,n2));
   return 0;
}

int hcf(int n1, int n2)
{
    if (n2 != 0)
       return hcf(n2, n1%n2);
    else 
       return n1;
}

Output

Enter two positive integers: 366
60
G.C.D of 366 and 60 is 6.

Check out these related examples:

• C Program to Add Two Integers
• C Program to Find the Sum of Natural Numbers using Recursion
• C Program to Find Factorial of a Number Using Recursion