C++ Code Example: greatest common divisor (recursion)

This code implements the Euclidean algorithm to find the greatest common divisor (GCD) of two numbers a and b. The GCD is the largest positive integer that divides two or more numbers without leaving a remainder.

The function gcd(int a, int b) takes two integer inputs a and b. The function uses recursion to calculate the GCD by repeatedly subtracting the smaller number from the larger number until either a or b is equal to zero. At that point, the other number will be returned as the GCD.

In each iteration of the function, the GCD is calculated by comparing a and b. If a is equal to zero, then b is returned as the GCD. If b is equal to zero, then a is returned as the GCD. If a is greater than b, then gcd(a-b,b) is called, subtracting b from a and keeping b unchanged. If b is greater than a, then gcd(a,b-a) is called, subtracting a from b and keeping a unchanged.

In the main function, two integer variables a and b are initialized with values 90 and 60 respectively. The GCD of a and b is calculated by calling the gcd function and the result is printed to the console.

#include <iostream>
using namespace std;

static int gcd(int a, int b) {
    if (a == 0) {
        return b;
    } else if (b == 0) {
        return a;
    } else if (a > b) {
        return gcd(a - b, b);
    } else {
        return gcd(a, b - a);
    }
}

int main() {
    int a = 90, b = 60;

    cout << "Greatest common divisor is: " << gcd(a, b) << endl;

    return 0;
}

Output

Greatest common divisor is: 30