CMMDC recursiv a două numere naturale în C++

Dându-se două numere naturale a și b, vrem să aflăm CMMDC-ul (cel mai mare divizor comun) al celor două numere.

Exemplu: pentru a = 4, b = 6, cmmdc(a, b) = 2.

În acest articol vom aborda o soluție folosind o funcție recursivă.

Soluția 1

În primul rând, căutăm cazurile de bază:

• Pentru a = 0 sau b = 0, cmmdc(a, 0) = cmmdc(0, b) = 0;
• Pentru a = b, cmmdc(a, b) = cmmdc(a, a) = a;

De asemenea, observăm că cmmdc(a, b) = cmmdc(a - b, b) (considerând a > b).

Cu aceste observații, putem să construim ușor funcția de CMMDC recursiv:

#include <iostream>

using namespace std;

int cmmdcRec(int a, int b) {
    if(a == 0 || b == 0) {
        //Primul caz de bază: cmmdc(a, 0) = 0
        return 0;
    }
    if(a == b) {
        //Al doilea caz de bază: cmmdc(a, a) = a
        return a;
    }
    //Conform observației de mai sus,
    //cmmdc(a, b) = cmmdc(a - b, b), pt a > b
    //cmmdc(a, b) = cmmdc(a, b - a), pt a < b
    if(a > b) {
        return cmmdcRec(a - b, b);
    } else {
        return cmmdcRec(a, b - a);
    }
}

int main()
{
    int a, b;
    cin >> a >> b;
    cout << "cmmdc(" << a << ", " << b << ") = " << cmmdcRec(a, b);
    return 0;
}

Soluția 2 (algoritmul lui Euclid)

Prima soluție merge, însă are complexitate liniară (O(n)). Folosind algoritmul lui Euclid, putem să optimizăm soluția de mai devreme, astfel:

#include <iostream>

using namespace std;

int cmmdcRec(int a, int b) {
    if(b == 0) {
        return a;
    }
    return cmmdcRec(b, a % b);
}

int main()
{
    int a, b;
    cin >> a >> b;
    cout << "cmmdc(" << a << ", " << b << ") = " << cmmdcRec(a, b);
    return 0;
}

A doua soluție poate fi un pic mai greu de înțeles, însă este mai scurtă.