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ă.