Question

Write a C++ program that reads in two integers and then computes the greatest common divisor GCD using recursion. DO NOT USE A BUILT-IN FUNCTION SUCH AS "gcd" to do this.

Answer 1

#include <iostream>
using namespace std;
// Recursive function to return gcd of a and b
int gcd(int a, int b)
{
if (a == 0)
return b;
if (b == 0)
return a;
if (a == b)
return a;

if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
int main()
{
int a,b;
cout<<"Enter two integers : ";
cin>>a>>b;
cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
return 0;
}

OUTPUT:-

Success #stdin #stdout Os 4244KB Enter two integers : 42 24 GCD of 42 and 24 is 6

// If any doubt please comment