#044 · Subiectul II · Programare

Cel mai mare divizor comun a două numere, folosind o funcție recursivă

✓ Rezolvare explicatăDolj 2026 · nr. 37

Enunț

Se citesc 2 numere naturale nenule x şi y de la tastatură. Folosind o funcţie recursivă, să se determine cel mai mare divizor comun al celor 2 numere naturale.

Exemple

Date de intrare	Date de ieșire	Explicații
`48 36`	`12`	12 este cel mai mare număr care îi împarte exact pe amândoi
`13 17`	`1`	Numere prime între ele

Rezolvare

C++

#include <iostream>
using namespace std;

int cmmdc(int x, int y) {
    if (y == 0) return x;               // cazul de baza
    return cmmdc(y, x % y);             // algoritmul lui Euclid
}

int main() {
    int x, y;
    cin >> x >> y;
    cout << cmmdc(x, y);
    return 0;
}

Cum funcționează

Rezolvarea folosește algoritmul lui Euclid, una dintre cele mai vechi metode din matematică, și merită înțeleasă, nu memorată — apare și la fracții ireductibile, și la c.m.m.m.c.

Ideea de bază: cel mai mare divizor comun al lui x și y este același cu cel al lui y și restul împărțirii lui x la y. Dacă un număr îi împarte exact și pe x, și pe y, atunci împarte exact și ce rămâne din x după ce scazi din el multipli de y — adică restul.

La fiecare apel numerele scad rapid, până când al doilea ajunge 0. În acel moment primul este chiar răspunsul: c.m.m.d.c. dintre un număr și 0 este numărul însuși, pentru că orice număr împarte exact pe 0.

Pentru x = 48, y = 36:

cmmdc(48, 36) → 48 % 36 = 12  →  cmmdc(36, 12)
cmmdc(36, 12) → 36 % 12 = 0   →  cmmdc(12, 0)
cmmdc(12, 0)  → y == 0        →  return 12

Observă că nu contează ordinea în care dai numerele. Dacă apelezi cmmdc(36, 48), primul pas calculează 36 % 48 = 36 și obține cmmdc(48, 36) — adică exact cazul de dinainte. Algoritmul se „așază" singur, deci nu trebuie să verifici care număr e mai mare.

Greșeli frecvente

if (x == 0) return y; cu apelul lăsat cmmdc(y, x % y) — condiția de oprire nu se mai potrivește cu ce se micșorează, iar recursivitatea nu se termină.
Folosirea scăderii repetate (cmmdc(x - y, y)) — matematic e corect, dar pentru numere precum 1.000.000 și 1 face un milion de apeluri și programul se blochează. Cu % sunt câțiva pași.
Împărțirea la zero — apare doar dacă muți x % y înaintea verificării y == 0. Cazul de bază se scrie primul, întotdeauna.
Rezolvarea iterativă cu while — enunțul cere explicit funcție recursivă.

Exersează mai departe

Probleme cu aceeași tehnică

#072ProgramareProdusul cifrelor unui număr, folosind o funcție recursivă #076ProgramareSuma cifrelor unui număr, folosind o funcție recursivă #573ProgramareNumere cu prima cifră pătrat perfect, ordonate descrescător (p_cifra recursiv și sortare)#581ProgramareNumărul prim cu cele mai multe cifre pare dintr-o matrice (prim și contorizare recursiv)#043ProgramareSă se calculeze şi să se afişeze cel mai mare divizor comun al elementelor vectorului #047ProgramareSă se afişeze două numere naturale prime a căror sumă este numărul n