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

In this post, you will learn how to Program to Find G.C.D Using Recursion in C++ programming language.

This lesson will teach you how to Program to Find G.C.D Using Recursion, with a recursion statement, mathematical operations and decision making statement using the C++ Language. Let’s look at the below source code.

How to Find G.C.D Using Recursion?

Source Code

#include<iostream>
using namespace std;
int gcd(int a, int b) 
{
   if (a == 0 || b == 0)
   return 0;
   else if (a == b)
   return a;
   else if (a > b)
   return gcd(a-b, b);
   else return gcd(a, b-a);
}
int main() 
{
   int a, b;
   cin>>a>>b;
   cout<<"Enter two positive numbers: "<<a<<","<<b<<endl;
   cout<<"\nGCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
   return 0;
}

Input

63
42

Output

Enter two positive numbers: 63,42
GCD of 63 and 42 is 21

The statements #include<iostream>, using namespace std, int main are the main factors that support the function of the source code. Now we can look into the working and layout of the code’s function.

1. In mathematics, the greatest common divisor of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. This is the Greatest Common Devisor – GCD of two numbers.
2. In this code we have two sections, in the first one we declare the function int gcd(int a, int b) to initiate the recursive function, where we declare the variables a and bas an integers.
3. Using if else if ladder we create multiple else if functions and statements;
   if (a == 0 || b == 0)
 the condition with the statement return 0
else if (a == b)the condition with the statement return a
else if (a > b)the condition with the statement return gcd(a-b, b)
else return gcd(a, b-a) as the last statement in the if else if ladder. 
4. The if statement is executed and the condition is verified, if the condition is false it moves to the next else if statement and when a condition is satisfied the statement/function is executed.
5. The function is repeated with the recursion and the GCD of the two numbers is found.
6. The function then moves to the output section of the code, where we use output statements to display the answer stored in gcd(a, b)

Note: The ‘ << endl ‘ in the code is used to end the current line and move to the next line and ‘\n’ is also a new line function, to understand how both the functions work exclude it from the code, move it around and work with it.