C++ Program to Find GCD using Recursion

Problem: Write a C++ program to find the Greatest Common Divisor (GCD) of two numbers using Recursion.

#include <iostream>

//Function to find the GCD/HCF using recursion
int gcd(int a, int b) {
    //Base case
    if (b == 0) {
        return a;
    }
    //Recursive case
    return gcd(b, a % b);
}

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

Output:

Enter two positive numbers: 9 27
GCD of 9 and 27 is 9

This program finds the greatest common divisor (GCD) of two numbers using the Euclidean algorithm.

The Euclidean algorithm is based on the property that the GCD of two numbers is the same as the GCD of the smaller number and the remainder when the larger number is divided by the smaller number.

The gcd function accepts two integers a and b as its parameters. The function uses a if statement to check if b is equal to zero, if true the function return a as GCD. If b is not zero, it returns the recursive call of gcd(b, a % b) which is the GCD of b and a%b.

In main function, the program prompts the user to enter two numbers, reads them, and then calls the gcd function to find the GCD of the two numbers. The GCD is then printed as output to the console.