Sari la conținut
Atestia
Exersează
Înapoi la teorie

Teorie

Recursivitate în C++ la atestatul de informatică — cazul de bază, pasul recursiv, funcții pe cifre și pe tablouri

Cum scrii o funcție recursivă cerută la atestat: cazul de bază și pasul recursiv, elementul neutru, recursivitatea pe cifre, algoritmul lui Euclid și recursivitatea pe tablouri — cu urmărirea apelurilor și problemele în care apar.

6

minute de citit

9

secțiuni

6

probleme rezolvate legate

Actualizat pe .

Pe această pagină
  1. Scheletul: cazul de bază și pasul recursiv
  2. Tehnica 1 — Recursivitate care acumulează: elementul neutru
  3. Tehnica 2 — Recursivitate care coboară: răspunsul e în cazul de bază
  4. Tehnica 3 — Doi parametri: algoritmul lui Euclid
  5. Tehnica 4 — Recursivitate pe un tablou: n scade cu 1
  6. Când recursivitatea e o idee proastă
  7. Greșeli care se repetă
  8. Unde exersezi mai departe
  9. Toate problemele din această categorie

La atestat, recursivitatea nu apare ca subiect separat, ci ca o condiție pusă unui subprogram: „folosind o funcție recursivă, calculați suma cifrelor”, „p_cifra (implementat recursiv) returnează prima cifră”. Rezultatul ar ieși la fel de bine cu un while — dar enunțul cere recursivitate, iar varianta iterativă nu primește punctajul subpunctului, chiar dacă dă răspunsul corect.

Vestea bună: toate cele șase probleme din sesiunile Dolj 2026 și Bucureşti 2020 folosesc același schelet de trei rânduri. Pagina îl explică o dată, apoi arată cele patru variante în care apare.

Scheletul: cazul de bază și pasul recursiv

Orice funcție recursivă are două părți:

  1. cazul de bază — situația în care răspunsul se știe direct, fără alt apel;
  2. pasul recursiv — funcția se apelează pe o variantă mai mică a aceleiași probleme și își construiește rezultatul din răspunsul primit.
C++
int sumaCifrelor(int n) {
    if (n == 0) return 0;                    // cazul de baza: nu mai sunt cifre
    return n % 10 + sumaCifrelor(n / 10);    // ultima cifra + suma celorlalte
}

Ca să verifici o funcție recursivă, urmărește apelurile pe hârtie. Ele coboară până la cazul de bază, iar rezultatele se combină la întoarcere:

sumaCifrelor(3815) = 5 + sumaCifrelor(381)
sumaCifrelor(381)  = 1 + sumaCifrelor(38)
sumaCifrelor(38)   = 8 + sumaCifrelor(3)
sumaCifrelor(3)    = 3 + sumaCifrelor(0)
sumaCifrelor(0)    = 0            <- cazul de baza
                                  -> 0 + 3 + 8 + 1 + 5 = 17

Două reguli fără excepție:

  • Cazul de bază se scrie primul. Fără el, funcția se apelează la nesfârșit, iar programul se oprește cu stack overflow.
  • Fiecare apel trebuie să se apropie de cazul de bază. n / 10 scurtează numărul cu o cifră, deci ajunge sigur la 0. Cu n / 10.0 (împărțire reală), nu mai ajunge niciodată.

Exersează pe subiecte reale

suma cifrelor, recursiv

Tehnica 1

Recursivitate care acumulează: elementul neutru

Când funcția adună, numără sau înmulțește ceva, cazul de bază întoarce elementul neutru al operației — valoarea care nu schimbă rezultatul:

Operația Cazul de bază întoarce Exemplu
sumă 0 suma cifrelor
numărare 0 câte cifre pare are numărul
produs 1 produsul cifrelor, produsul diagonalei
C++
int produsCifrelor(int n) {
    if (n == 0) return 1;                    // 1, nu 0: la inmultire, 0 "inghite" tot
    return n % 10 * produsCifrelor(n / 10);
}

Cu return 0, produsul iese 0 pentru orice număr — greșeala cea mai depunctată la aceste probleme. (Dacă numărul chiar conține cifra 0, de exemplu 305, produsul este 0; nu e o eroare.)

Numărarea se scrie la fel, adunând rezultatul unei condiții — în C++, o comparație valorează 1 dacă e adevărată și 0 dacă e falsă:

C++
int contorizare(int y) {                       // cate cifre pare are y
    if (y == 0) return 0;
    return (y % 10 % 2 == 0) + contorizare(y / 10);
}

Exersează pe subiecte reale

produsul cifrelornumărul prim cu cele mai multe cifre pare

Tehnica 2

Recursivitate care coboară: răspunsul e în cazul de bază

Nu orice funcție recursivă combină ceva la întoarcere. Ca să afli prima cifră a unui număr, tai ultima cifră până rămâne una singură — iar aceea e chiar răspunsul:

C++
int p_cifra(int y) {
    if (y < 10) return y;              // o singura cifra: ea e prima
    return p_cifra(y / 10);            // nimic de adaugat, doar coboram
}

p_cifra(48903) → p_cifra(4890) → p_cifra(489) → p_cifra(48) → p_cifra(4) = 4.

Aici cazul de bază nu e y == 0: coborând până la 0, funcția ar întoarce mereu 0. Întrebarea de pus e „când știu răspunsul direct?” — la sumă, când nu mai sunt cifre (0); la prima cifră, când a rămas una (y < 10).

Exersează pe subiecte reale

numere cu prima cifră pătrat perfect

Tehnica 3

Doi parametri: algoritmul lui Euclid

C.m.m.d.c.-ul are o definiție recursivă aproape gata scrisă: c.m.m.d.c.(x, y) = c.m.m.d.c.(y, x % y), iar c.m.m.d.c.-ul unui număr cu 0 e numărul însuși.

C++
int cmmdc(int x, int y) {
    if (y == 0) return x;
    return cmmdc(y, x % y);
}
cmmdc(48, 36) -> cmmdc(36, 12) -> cmmdc(12, 0) = 12

Ordinea parametrilor nu contează: cmmdc(36, 48) face întâi cmmdc(48, 36) și continuă la fel. Contează însă ca testul din cazul de bază să fie pe parametrul care se micșorează — y, care devine x % y. Cu if (x == 0) return y; recursivitatea nu se mai termină.

Varianta cu scăderi (cmmdc(x - y, y)) e corectă matematic, dar pentru 1000000 și 1 face un milion de apeluri. Ideea e explicată pe larg la algoritmul lui Euclid.

Exersează pe subiecte reale

c.m.m.d.c. recursiv

Tehnica 4

Recursivitate pe un tablou: n scade cu 1

Același schelet merge și pe tablouri: în loc să tai o cifră, tai ultimul element. Produsul elementelor de pe diagonala principală a unei matrici n × n e a[n][n] înmulțit cu produsul diagonalei matricei de dimensiune n - 1:

C++
double produs(double a[21][21], int n) {
    if (n == 0) return 1;                      // produsul vid
    return a[n][n] * produs(a, n - 1);
}

Pentru diagonala 3, 2, 1: produs(a, 3) = 1 · produs(a, 2) = 1 · 2 · produs(a, 1) = 1 · 2 · 3 · 1 = 6.

Parametrul care scade e dimensiunea, nu tabloul — tabloul se transmite neschimbat la fiecare apel. Cazul de bază n == 0 presupune indexarea de la 1; cu indexare de la 0, elementul curent e a[n-1][n-1].

Exersează pe subiecte reale

determinantul matricei inferior triunghiulare

Când recursivitatea e o idee proastă

Recursivitatea e corectă oriunde, dar nu e mereu rezonabilă. Șirul lui Fibonacci scris recursiv (fib(n - 1) + fib(n - 2)) recalculează aceiași termeni de foarte multe ori și devine inutilizabil deja pe la n = 45 — vezi șirurile recurente. Regula practică la atestat: scrie recursiv doar ce enunțul cere explicit recursiv; restul, cu bucle.

Greșeli care se repetă

  • Lipsa cazului de bază sau scris după apelul recursiv — stack overflow
  • return 0 la produs — rezultatul e 0 pentru orice număr; produsul începe de la 1
  • Cazul de bază greșit ales — y == 0 la „prima cifră” întoarce mereu 0
  • Testul pe parametrul care nu scade — la Euclid, x == 0 în loc de y == 0
  • Împărțire reală (n / 10.0) — numărul nu mai ajunge la 0
  • Rezolvare iterativă când enunțul cere recursiv — rezultat corect, punctaj pierdut
  • Scăderi repetate în loc de % — corect, dar prea lent pe numere mari

Mai departe

Unde exersezi mai departe

Cel mai bun exercițiu e urmărirea apelurilor pe hârtie: ia oricare dintre funcțiile de mai sus, alege un număr și scrie tabelul de apeluri înainte să rulezi programul. Dacă tabelul tău și programul dau același rezultat, ai înțeles mecanismul.

Pe pbinfo.ro găsești probleme de recursivitate cu evaluator automat, pe cifre, pe tablouri și pe șiruri.

Toate problemele din această categorie

Fiecare are rezolvare completă în C++, cu urmărirea apelurilor.

6Arată toate problemele rezolvate6 programare

Alte pagini de teorie

Sortare și ordonare în C++21Baze de date în Access90Baze de date şi SQL81Date structurate8Lucrul cu fișiere în C++90Formatarea documentelor Word39Formule și funcții Excel51Grafuri și arbori6Interogări SQL pe două tabele91Matrici51Modelul entitate-relație25Numere și divizibilitate127Prezentări PowerPoint23Șiruri de caractere38Șiruri recurente7Sisteme de operare41Vectori59