C program to find GCD (HCF) of two numbers using recursion

Functions Exercises

C Basics C Programming Tutorial Basic C Exercises Bitwise Operator Exercises Conditional Operator Exercises If else Exercises Switch case Exercises Loop Exercises Star Patterns Number Patterns Functions Exercises Array Exercises String Exercises Pointer Exercises File handling Exercises Data Structures

• C Programming Exercises
• Basic C programming exercises
• Bitwise operator exercises
• Conditional operator exercises
• If else exercises
• Switch case exercises
• Loop and iteration exercises
• Star patterns exercises
• Number pattern exercises
• Functions and recursion exercises
• Array and Matrix exercises
• String exercises
• Pointer exercises
• Files handling exercises

C program to find GCD (HCF) of two numbers using recursion

Write a recursive function in C to find GCD (HCF) of two numbers. How to find GCD(Greatest Common Divisor) or HCF(Highest Common Factor) of two numbers using recursion in C program. Logic to find HCF of two numbers using recursion in C programming.

Required knowledge

Basic C programming, If else,for loop,Functions, Recursion

Logic to find GCD using recursion

Here in this program we will be using recursive approach of Euclidean algorithm to find GCD of two numbers. The Euclidean algorithm to find GCD is,

Algorithm to find GCD using Euclidean algorithm

Begin:
function gcd(a, b)
    If (b = 0) then
       return a
    End if 
    Else
       return gcd(b, a mod b);
    End if
End function
End

Program to find HCF of two numbers using recursion

 
/**
 * C program to find GCD (HCF) of two numbers using recursion
 */
 
#include <stdio.h>

/* Function declaration */
int gcd(int a, int b);


int main()
{
    int num1, num2, hcf;
    
    /* Input two numbers from user */
    printf("Enter any two numbers to find GCD: ");
    scanf("%d%d", &num1, &num2);
    
    hcf = gcd(num1, num2);
    
    printf("GCD of %d and %d = %d", num1, num2, hcf);
    
    return 0;
}


/**
 * Recursive approach of euclidean algorithm to find GCD of two numbers
 */
int gcd(int a, int b)
{
    if(b == 0)
        return a;
    else
        return gcd(b, a%b); 
}

Output

Enter any two numbers to find GCD: 12

30

GCD of 12 and 30 = 6

Follow @NEWSPAPERS_NEW

C Programming