Program to Find GCD or HCF of Two Numbers using Recursion - C, C++ Code

Write a program to find GCD or HCF of  two numbers. In this tutorial, we are going to write following programs.

• Write a C program to find GCD or HCF of two numbers.
• Write a C++ program to find GCD or HCF of two numbers.

In this example, our program will take two input integer and then compute it's GCD or HCF using recursion. If you don't know about recursion then read this awesome post on recursion vs iteration.

What is GCD (Greatest Common Divisior) or HCF (Highest Common Factor) ?

GCD or HCF of two  numbers is the largest number which divides both the number without leaving any remainder.

Binary Search program in C, C++

Let's take an example -

Take two numbers 63 and 21.

Divisible of 63 is 3, 7, 9, 21 ,63

Divisible of 21 is 3, 7, 21

Highest Divisible of both the numbers without leaving any remainder is 21.

Check whether number is Armstrong or not

C++ Program to Find GCD of Two Numbers using Recurison

#include <iostream>
using namespace std;

int gcd(int a, int b) {
 
    // If b is zero
    if(b == 0){
       return a;
    }
 
    return gcd(b, a%b);
}

int main() {
 
     int num1, num2, result;
 
     cout << "Enter two numbers \n";
     cin  >> num1 >> num2;
 
     result = gcd(num1, num2);
 
     cout << "GCD of two numbers is " << result;
 
     return 0;
}

C Program to Find GCD of Two Numbers using Recursion

#include <stdio.h>

int gcd (int a, int b) {

      /* If b is equal to zero. */

      if(b == 0) {
          return a;
      }
      
      // Recursive call
      
      gcd(b, a%b);
}

int main(void) {

  int a, b, g;
 
  printf("Enter two numbers \n");
  scanf("%d %d",&a, &b);
 
  g =  gcd(a, b);
 
  printf("GCD of two numbers %d %d is %d",a,b,g);
 
  return 0;
}

Output :


Enter two numbers  :   15    25

GCD of two numbers is  :  5

Programming question on Arrays

Programming question on Linked List

Sorting algorithm and their time complexity

Stack implementation

Programming questions using Recursion

C, C++ interview questions

Programming Books

Popular Data Structure Books