SISergiu Ilincameditații informatică
Meniu

clasa a XI-a · Recursivitate · lecția 3

Recursivitate (1): mecanism, stivă, funcții recursive simple

60 minmate-info

Înainte de lecția asta: XI.2 Subprograme (2): parametri prin referință și subprograme cu tablouri

Ce vei ști după lecție

  • Înțelegi ce este o funcție recursivă: condiția de oprire + apelul pentru o problemă mai mică.
  • Urmărești execuția unei funcții recursive pe stivă (arborele de apeluri).
  • Scrii recursiv: factorial, putere, cmmdc, suma și numărul cifrelor, cifra maximă.
  • Rezolvi grilele de tip „ce valoare are f(…)?” și „ce afișează apelul…?”.

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Clasa a XI-aLecția 3 din 21 · mai sunt 18Urmează: XI.4 · Recursivitate (2): pe vectori, pe șiruri și algoritmul de umplere (fill)Vezi toate lecțiile
Cuprins

Fișiere PDF și de lucru

1. Ideea: problema mare = problema mică + un pas

O funcție este recursivă dacă se apelează pe ea însăși. Gândește-te la factorial: 5! = 5 · 4!, iar 4! = 4 · 3!, și tot așa până la 0! = 1. Soluția pentru n se obține din soluția aceleiași probleme pentru n − 1.

long long fact(int n)
{
    if (n == 0) return 1;           // 1) cazul de bază: răspunsul îl știm direct
    return n * fact(n - 1);         // 2) pasul recursiv: o problemă mai mică
}

Stiva de apeluri

Orice funcție recursivă corectă are două ingrediente:

  1. cazul de bază (condiția de oprire): situația în care răspunsul e cunoscut și nu mai apelăm;
  2. pasul recursiv: un apel pe o problemă strict mai mică, care se apropie de cazul de bază.

De ce așa?

De ce funcționează? Presupunem că fact(n − 1) ne dă corect răspunsul (acesta e „actul de credință” al recursivității) și doar îl completăm cu pasul n *. Cazul de bază ne asigură că lanțul de apeluri se termină.

Capcană

Fără caz de bază (sau dacă apelul nu se apropie de el), funcția se apelează la nesfârșit până se umple memoria alocată stivei: stack overflow. Verifică mereu: există un caz de bază? Fiecare apel se apropie de el?

#include <iostream>
using namespace std;

long long fact(int n)
{
    if (n == 0) return 1;
    return n * fact(n - 1);
}

int main()
{
    int n;
    cin >> n;
    cout << fact(n);
    return 0;
}

Intrare / ieșire

Intrare Ieșire
5 120
0 1
20 2432902008176640000

2. Ce se întâmplă în memorie: stiva

Fiecare apel primește propriul „cadru” pe stivă, cu propriile copii ale parametrilor și variabilelor locale. Apelurile se adâncesc până la cazul de bază (coborâre), apoi se întorc în ordine inversă, fiecare terminându-se cu rezultatul calculat (urcare). Vezi figura de mai sus: fact(3) așteaptă fact(2), care așteaptă fact(1), care așteaptă fact(0).

moment cadre pe stivă (sus = cel mai nou)
după main apelează fact(3) fact(3)
fact(3) apelează fact(2) fact(3), fact(2)
fact(2) apelează fact(1) fact(3), fact(2), fact(1)
fact(1) apelează fact(0) fact(3), fact(2), fact(1), fact(0)
fact(0) returnează 1 fact(3), fact(2), fact(1)
fact(1) returnează 1·1 = 1 fact(3), fact(2)
fact(2) returnează 2·1 = 2 fact(3)
fact(3) returnează 3·2 = 6 (gol)

3. Funcții recursive pe cifre

Ideea: ultima cifră (n % 10) + restul numărului (n / 10), care este o problemă mai mică.

#include <iostream>
using namespace std;

int sumaCif(int n)
{
    if (n == 0) return 0;                 // fără cifre: suma 0
    return n % 10 + sumaCif(n / 10);
}

int nrCif(int n)
{
    if (n < 10) return 1;                 // o singură cifră
    return 1 + nrCif(n / 10);
}

int cifMax(int n)
{
    if (n < 10) return n;
    int m = cifMax(n / 10);               // cea mai mare cifră din restul numărului
    return (n % 10 > m) ? n % 10 : m;
}

int main()
{
    int n;
    cin >> n;
    cout << sumaCif(n) << ' ' << nrCif(n) << ' ' << cifMax(n);
    return 0;
}

Urmărire pentru sumaCif(4075):

apel n % 10 rest n / 10 returnează
sumaCif(4075) 5 407 5 + sumaCif(407) = 5 + 11 = 16
sumaCif(407) 7 40 7 + sumaCif(40) = 7 + 4 = 11
sumaCif(40) 0 4 0 + sumaCif(4) = 0 + 4 = 4
sumaCif(4) 4 0 4 + sumaCif(0) = 4 + 0 = 4
sumaCif(0) 0 (caz de bază)

De ce așa?

De ce cazul de bază diferă la sumaCif (n == 0) și nrCif (n < 10)? Suma cifrelor „fără nicio cifră” are sens (0), dar numărul de cifre al lui 0 nu este 0, ci 1 (scrisul „0” are o cifră). Alege cazul de bază care dă o valoare corectă pentru cea mai mică intrare a problemei.

Cmmdc și puterea

Algoritmul lui Euclid este recursiv prin natura lui: cmmdc(a, b) = cmmdc(b, a mod b).

#include <iostream>
using namespace std;

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

long long putere(long long a, int n)        // a^n în O(log n) pași
{
    if (n == 0) return 1;
    long long p = putere(a, n / 2);          // calculat O SINGURĂ DATĂ
    if (n % 2 == 0) return p * p;
    return p * p * a;
}

int main()
{
    int a, b, n;
    long long x;
    cin >> a >> b >> x >> n;
    cout << cmmdc(a, b) << ' ' << putere(x, n);
    return 0;
}

De ce așa?

De ce putere face doar log n pași? Folosim 2^10 = (2^5)^2 și 2^5 = (2^2)^2 · 2: de fiecare dată jumătate din exponent. Dacă am fi scris putere(a, n/2) * putere(a, n/2), am fi calculat de două ori aceeași valoare și am fi ajuns tot la n pași. Variabila p păstrează rezultatul.

Urmărire pentru putere(2, 5):

apel n p (după apel) returnează
putere(2, 5) 5 putere(2, 2) = 4 4 · 4 · 2 = 32
putere(2, 2) 2 putere(2, 1) = 2 2 · 2 = 4
putere(2, 1) 1 putere(2, 0) = 1 1 · 1 · 2 = 2
putere(2, 0) 0 1

4. Afișarea „la coborâre” vs. „la urcare”

Locul instrucțiunii cout față de apelul recursiv schimbă ordinea!

Ordinea afișării

#include <iostream>
using namespace std;

void f(int n)
{
    if (n == 0) return;
    cout << n % 10;      // ÎNAINTE de apel: cifrele de la dreapta la stânga
    f(n / 10);
}

void g(int n)
{
    if (n == 0) return;
    g(n / 10);
    cout << n % 10;      // DUPĂ apel: cifrele de la stânga la dreapta
}

int main()
{
    int n;
    cin >> n;
    f(n); cout << '\n';
    g(n);
    return 0;
}

De ce așa?

De ce g afișează în ordinea corectă? g(123) așteaptă să se termine g(12), care așteaptă g(1). Primul cout care se execută este cel din g(1) (afișează 1), apoi g(12) afișează 2, apoi g(123) afișează 3. Stiva răstoarnă ordinea, la fel ca un teanc de farfurii: ultima pusă e prima luată.

Acesta este exact tipul de grilă de la Subiectul I: o funcție cu cout înainte și/sau după apel.

#include <iostream>
using namespace std;

void h(int n)
{
    if (n > 0)
    {
        cout << n;
        h(n - 2);
        cout << n;
    }
}

int main()
{
    h(5);
    return 0;
}

Urmărire pentru h(5):

apel afișează înainte apelează afișează după
h(5) 5 h(3) 5
h(3) 3 h(1) 3
h(1) 1 h(-1) 1
h(-1) (n > 0 fals, nu face nimic)

Ordinea în timp: 5, 3, 1 (la coborâre), apoi 1, 3, 5 (la urcare) → 531135.

La BAC

La grile desenează arborele (lanțul) de apeluri și notează ce se afișează la coborâre și ce se afișează la urcare. Citirea „pe diagonală” a codului duce la greșeli.

5. Funcții care întorc o valoare: „cât este f(…)”

#include <iostream>
using namespace std;

int calls = 0;

int f(int x)
{
    calls++;                           // numărăm câte apeluri se fac
    if (x <= 1) return x;
    return f(x - 1) + f(x - 2);
}

int main()
{
    int n;
    cin >> n;
    cout << f(n) << ' ' << calls;
    return 0;
}

Arborele de apeluri

f(4) = f(3) + f(2); arborele arată că f(2) se calculează de două ori, iar f(1) de trei ori. Pentru n = 10 programul face 177 de apeluri ca să afle 55; pentru n = 40 ar face sute de milioane.

De ce așa?

De ce e lent Fibonacci recursiv? Fiecare apel dă naștere la alte două, și aceleași valori se recalculează în ramuri diferite. Numărul de apeluri crește aproximativ ca 1,6ⁿ. Soluțiile: calculul iterativ (cu doi indici, ca la clasa a IX-a) sau programarea dinamică (lecția XI.16), care „ține minte” rezultatele.

Sfat

Pentru „cât este f(n)” calculează de jos în sus: f(0), f(1), f(2), … într-un tabel, până la n. Este mult mai rapid decât să desfaci tot arborele.

6. Recursiv sau iterativ?

Orice funcție recursivă se poate scrie și iterativ. Recursivitatea e naturală pentru probleme care „se definesc prin ele însele” (backtracking, divide et impera, arbori), dar consumă memorie pe stivă și, ca la Fibonacci, poate repeta calcule.

Recursiv Iterativ
claritate foarte clar pentru probleme recursive clar pentru bucle simple
memorie O(adâncimea apelurilor) pe stivă O(1) de obicei
viteză apelurile costă puțin de obicei mai rapid
risc stack overflow la adâncimi mari nu există

7. Greșeli frecvente

Greșeala Efect Corect
lipsește cazul de bază recursie infinită, stack overflow if (...) return …; la început
apelul nu se apropie de cazul de bază (f(n) în loc de f(n - 1)) recursie infinită micșorează problema
cazul de bază greșit (nrCif(0) = 0) răspunsuri greșite verifică pe cea mai mică intrare
cout la locul greșit ordine inversată pune-l înainte (coborâre) sau după (urcare)
dublezi apelul (putere(a, n/2) * putere(a, n/2)) timp O(n) salvează într-o variabilă
ai return doar într-o ramură valoare necunoscută return pe toate căile

8. La BAC

La BAC

La Subiectul I apar, aproape mereu, una–două grile cu subprograme recursive: „ce se afișează la apelul f(…)?” sau „care este valoarea lui f(…)?”. Metoda sigură: tabel cu coloane apel / afișează înainte / apelează / afișează după / returnează și se completează de sus în jos, apoi de jos în sus.

9. Exersează pe hârtie

Răspunsurile sunt la final: încearcă întâi singur.

1. Ce afișează g(4)?

void g(int n) { if (n) { g(n - 1); cout << n; g(n - 1); } }

2. Scrie o funcție recursivă care returnează numărul de cifre pare ale lui n (pentru n > 0).

3. Scrie o funcție recursivă care afișează reprezentarea în baza 2 a lui n.

4. Dacă int f(int x) { if (x <= 1) return x; return f(x - 1) + f(x - 2); }, cât este f(6)?

5. Ce se întâmplă la apelul int f(int n) { return n * f(n - 1); }?

6. Ce afișează h(4), cu h din secțiunea 4?

7. Calculează cmmdc(48, 18) scriind apelurile.

8. Câte apeluri face putere(2, 5)? Dar putere(2, 16)?

9. Cât returnează nrCif(0)? Justifică.

10. (BAC) Ce valoare are f(5)?

int f(int x) { if (x == 0) return 0; if (x % 2 == 1) return x + f(x - 1); return f(x - 1); }

10. Mai departe (pentru cine vrea mai mult)

Citire și afișare inversă fără vector. Stiva de apeluri poate „ține minte” valorile citite:

#include <iostream>
using namespace std;

void citeste(int k)
{
    if (k == 0) return;
    int x;
    cin >> x;               // citim și păstrăm x în cadrul acestui apel
    citeste(k - 1);         // citim restul
    cout << x << ' ';       // la urcare afișăm: ordine inversă
}

int main()
{
    int n;
    cin >> n;
    citeste(n);
    return 0;
}

Recursivitate de coadă (tail recursion). Dacă apelul recursiv este ultima operație (return cmmdc(b, a % b);), compilatorul poate transforma automat funcția într-o buclă, fără consum de stivă.

Funcția lui Ackermann. Un exemplu celebru de funcție recursivă care crește uimitor de repede: A(3, 3) = 61, dar A(4, 2) are zeci de mii de cifre. O verifici ca exercițiu, dar nu cu valori mari!

Fractali. Triunghiul lui Sierpinski, fulgul lui Koch și alte desene se definesc recursiv: o figură este făcută din copii mai mici ale ei însăși. Caută „recursion fractal C++” pentru exemple.

Rezumat

  • Recursivitate = caz de bază + apel pe o problemă mai mică.
  • Fiecare apel are propriile variabile, pe stivă; apelurile se termină în ordine inversă.
  • cout înainte de apel → la coborâre; după apel → la urcare (ordine inversă).
  • Fibonacci recursiv simplu refăcut același calcul de multe ori; folosește iterativ sau programare dinamică.
  • Verifică mereu: cazul de bază corect, apel care se apropie de el.

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 6 pagini · 100 min

Recursivitate: stiva de apeluri, cifre, vectori, fill

  • Urmărești pe stivă orice funcție recursivă și spui exact ce afișează sau ce returnează (grila de la Subiectul I).
  • Repari funcțiile recursive greșite: caz de bază, apel care nu se apropie, parametru prin valoare în loc de referință.
  • Scrii recursiv prelucrări pe cifre, pe vectori și algoritmul de umplere (fill).

Fișa acoperă și: XI.4

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • factorialrec#820

    ușoară
  • cmmdcrec#821

    ușoară
  • sumcifrec#823

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • nrcifrezerorec#822

    ușoară
  • cifmaxrec#824

    ușoară
  • cifminrec#825

    ușoară
  • afisarerec#829

    Afișare în ordine inversă a valorilor citite — fără vector!

    ușoară
  • sumcifrec1#918

    ușoară
  • cifmaxminrec#920

    ușoară
  • difparimpar#4209

    ușoară

Pentru cei care vor mai mult

  • powerrec#1809

    ușoară
  • b16-rec#4042

    ușoară

Grile din subiectele de BAC

Exerciții de tip grilă din variantele de Bacalaureat. Se rezolvă pe pbinfo.ro, care îți verifică imediat răspunsul.

Citește și exersează în plus

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Exersează pe hârtie

1. 121312141213121. g(1) afișează 1; g(2) = g(1), 2, g(1) = 121; g(3) = 121, 3, 121 = 1213121; g(4) = 1213121, 4, 1213121.

2.

#include <iostream>
using namespace std;

int nrPare(int n)
{
    if (n == 0) return 0;
    return (n % 10 % 2 == 0) + nrPare(n / 10);     // expresia booleană valorează 0 sau 1
}

int main()
{
    int n;
    cin >> n;
    cout << nrPare(n);
    return 0;
}

3.

#include <iostream>
using namespace std;

void bin(int n)
{
    if (n > 1) bin(n / 2);      // mai întâi biții mai semnificativi (la urcare îi scriem)
    cout << n % 2;
}

int main()
{
    int n;
    cin >> n;
    bin(n);
    return 0;
}

4. f(6) = 8 (șirul 0, 1, 1, 2, 3, 5, 8).

5. Nu există caz de bază: funcția se apelează la infinit (f(n-1), f(n-2), … trece de 0 în numere negative), stiva se umple și programul se oprește cu stack overflow.

6. 4224: h(4) afișează 4, apelează h(2) (afișează 2, apelează h(0) care nu face nimic, apoi afișează 2) și apoi afișează 4.

7. cmmdc(48, 18) → cmmdc(18, 12) → cmmdc(12, 6) → cmmdc(6, 0) = 6.

8. putere(2, 5): apeluri pentru n = 5, 2, 1, 0: 4. putere(2, 16): n = 16, 8, 4, 2, 1, 0: 6. (Crește cu 1 la fiecare dublare a exponentului.)

9. 1. Cazul de bază n < 10 prinde și 0, iar numărul 0 se scrie cu o cifră.

10. 9: f(5) = 5 + f(4), f(4) = f(3), f(3) = 3 + f(2), f(2) = f(1), f(1) = 1 + f(0) = 1. Deci f(5) = 5 + 3 + 1 = 9 (suma numerelor impare până la 5).