2. Mecanismul de funcționare

Orice funcție recursivă corect scrisă trebuie să fie compusă din două elemente vitale. Dacă lipsește primul, programul va intra într-o buclă infinită și se va bloca!

1. Cazul de bază - Cazul trivial (Condiția de Oprire)

Este momentul în care funcția știe direct răspunsul, fără a se mai apela pe ea însăși. Când se ajunge aici, lanțul de apeluri se oprește și încep să se returneze rezultatele înapoi.

2. Pasul Recursiv (Auto-apelarea)

Este operația prin care funcția se apelează din nou, dar cu parametri modificați, apropiindu-se de Cazul de bază.

Stiva de Apeluri (Call Stack)

Calculatorul stochează starea funcției curente (variabilele locale și adresa de întoarcere) într-o zonă specială de memorie numită Stivă (Stack), care funcționează pe principiul LIFO (Last In, First Out).

Q1: Ce se va întâmpla dacă uităm să scriem "Cazul de bază" într-o funcție recursivă?

A) Compilatorul va genera automat o condiție de oprire. B) Programul va afișa valoarea 0. C) Memoria stivei se va umple până la prăbușirea programului (eroarea Stack Overflow).

Q2: Principiul LIFO (Last In, First Out) al Stivei de apeluri înseamnă că:

A) Primul apel adăugat în stivă este primul care se termină. B) Ultimul apel adăugat în stivă este primul care se va termina și va fi eliminat. C) Funcțiile sunt executate în ordine alfabetică.

Q3: Care dintre următoarele rânduri reprezintă PASUL RECURSIV într-o funcție?

A) if (n == 0) return 1; B) int s = 0; C) return n * factorial(n - 1);

3. Funcții Matematice Recursive

Factorialul unui număr ($n!$)

Matematic, pentru $n > 0$, avem recurența: $n! = n \cdot (n-1)!$, iar $0! = 1$.

Varianta Iterativă (Bucle)

 long fact_iterativ(int n) {
     long p = 1;
    for(int i = 1; i <= n; i++) {
        p = p * i;
    }
    return p;
}

Varianta Recursivă

 long fact_recursiv(int n) {
    if (n == 0) {
        return 1;
    }
    return ;
}

Șirul lui Fibonacci

Formula recurentă: $$F_n = F_{n-1} + F_{n-2}$$ cu cazurile de bază $F_0 = 1$ și $F_1 = 1$.

Scrie Cazul de Bază (condiția if) pentru funcția Fibonacci:

 long fibo(int n) {
    if (  ) {
        return n;
    }
    return fibo(n - 1) + fibo(n - 2);
}

Funcția lui Ackermann

Funcția lui Ackermann este celebră în informatică fiind un exemplu clasic de funcție recursivă cu o creștere extrem de rapidă (nu este primitiv recursivă). Pentru valori mici ale lui `m` și `n` (ex. m=4, n=2), aceasta epuizează instantaneu stiva de execuție, demonstrând forța brută a auto-apelărilor multiple!

long ackermann(long long m, long long n) {
    if (m == 0) return n + 1;
    if (m > 0 && n == 0) return ackermann(m - 1, 1);
    return ackermann(m - 1, ackermann(m, n - 1));
}

4. Operații pe Numere (Iterativ vs Recursiv)

Completează spațiile libere din variantele recursive pentru a finaliza algoritmii.

1. CMMDC - Prin scăderi repetate

Iterativ (while)

int cmmdc_scaderi_iter(int a, int b) {
    while (a != b) {
        if (a > b) a = a - b;
        else b = b - a;
    }
    return a;
}

Recursiv

int cmmdc_scaderi_rec(int a, int b) {
    if (  ) {
        return a;
    }
    if (a > b) return cmmdc_scaderi_rec(a - b, b);
    return cmmdc_scaderi_rec(a, b - a);
}

2. CMMDC - Prin împărțiri repetate (Alg. lui Euclid)

Știm matematic că $CMMDC(a, b) = CMMDC(b, a \% b)$.

Iterativ

int cmmdc_resturi_iter(int a, int b) {
    int r;
    while (b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Recursiv

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

3. Suma cifrelor unui număr

Iterativ

int sumaCifre_iter(int n) {
    int s = 0;
    while (n > 0) {
        s = s + n % 10;
        n = n / 10;
    }
    return s;
}

Recursiv

int sumaCifre_rec(int n) {
    if (n == 0) return 0;
    return n % 10 + sumaCifre_rec(  );
}

4. Oglinditul unui număr

Iterativ

int oglindit_iter(int n) {
    int inv = 0;
    while (n > 0) {
        inv = inv * 10 + n % 10;
        n = n / 10;
    }
    return inv;
}

Recursiv

int oglindit_rec(int n, int inv) {
    if (n == 0) return inv;
    return oglindit_rec(  );
}

5. Construirea unui număr doar din cifrele impare

Iterativ

int impare_iter(int n) {
    int p = 1, rez = 0;
    while (n > 0) {
        if ((n % 10) % 2 != 0) {
            rez = rez + (n % 10) * p;
            p = p * 10;
        }
        n = n / 10;
    }
    return rez;
}

Recursiv

int impare_rec(int n) {
    if (n == 0) return 0;
    if ((n % 10) % 2 != 0) {
        // Pun cifra in coada rezultatului venit de sus
        return impare_rec(n / 10) * 10 + ;
    }
    return impare_rec(n / 10);
}

6. Combinări ($C_n^k$)

Matematic: $C_n^k = C_{n-1}^k + C_{n-1}^{k-1}$.

Iterativ

long combinari_iter(int n, int k) {
    long rez = 1;
    for (int i = 1; i <= k; i++) {
        rez = rez * (n - i + 1) / i;
    }
    return rez;
}

Recursiv

 long combinari_rec(int n, int k) {
    if (k == 0 || k == n) return 1;
    return combinari_rec(n - 1, k) + combinari_rec();
}

5. Recursivitatea pe Vectori

Pentru a parcurge liniar un vector, tratăm problema asftel: un vector `v` cu `n` elemente este format din ultimul său element v[n-1] și un sub-vector de dimensiune n-1. Completează spațiile libere de mai jos.

1. Suma elementelor unui vector. Ce adunăm cu suma restului vectorului?

int sumaV(int v[], int n) {
    if (n == 0) return 0; 
    return  + sumaV(v, n - 1);
}

2. Suma doar pentru elementele PARE. Care este condiția?

int sumaPare(int v[], int n) {
    if (n == 0) return 0;
    if (  ) {
        return v[n - 1] + sumaPare(v, n - 1);
    } else {
        return sumaPare(v, n - 1);
    }
}

3. Produsul elementelor IMPARE. Ce trebuie să returneze cazul de bază pentru ca înmulțirile să funcționeze corect?

int prodImpare(int v[], int n) {
    if (n == 0) return ;
    if (v[n - 1] % 2 != 0) {
        return v[n - 1] * prodImpare(v, n - 1);
    }
    return prodImpare(v, n - 1);
}

4. Căutarea numărului de apariții ale valorii X. Cu cât mărim rezultatul când găsim o apariție?

int numarAparitii(int v[], int n, int x) {
    if (n == 0) return 0;
    if (v[n - 1] == x) {
        return  + numarAparitii(v, n - 1, x);
    }
    return numarAparitii(v, n - 1, x);
}

5. Maximul elementelor unui vector. Completează condiția pentru a actualiza maximul:

int maxVector(int v[], int n) {
    if (n == 1) return v[0]; 
    int m = maxVector(v, n - 1); // Salvez maximul din restul vectorului
    if (  ) {
        return v[n - 1];
    } else {
        return m;
    }
}

6. Minimul elementelor unui vector. Ce returnăm când vectorul are un singur element (n == 1)?

int minVector(int v[], int n) {
    if (n == 1) return ; 
    int m = minVector(v, n - 1); 
    if (v[n - 1] < m) {
        return v[n - 1];
    }
    return m;
}

Condiții compuse și parcurgeri speciale

7. Suma elementelor divizibile cu 3. Scrie condiția:

int sumaDiv3(int v[], int n) {
    if (n == 0) return 0;
    if (  ) {
        return v[n - 1] + sumaDiv3(v, n - 1);
    }
    return sumaDiv3(v, n - 1);
}

8. Contorul aparițiilor numerelor pare. Ce returnăm dacă numărul e par?

int contorPare(int v[], int n) {
    if (n == 0) return 0;
    if (v[n - 1] % 2 == 0) {
        return  + contorPare(v, n - 1);
    }
    return contorPare(v, n - 1);
}

6. Autoevaluare (15 itemi)

Apasă pe butonul "Verifică" pentru a afla dacă ai răspuns corect și pentru a vedea explicația pas cu pas.

1. Ce afișează apelul f(3)?

void f(int n) {
    if (n > 0) { cout << n; f(n - 1); }
}

2. Dar dacă afișarea se face DUPĂ apel: f(3)?

void f(int n) {
    if (n > 0) { f(n - 1); cout << n; }
}

3. Ce afișează apelul baza(5)?

void baza(int n) {
    if (n > 0) { cout << n % 2; baza(n / 2); }
}

4. Ce returnează calcul(135)?

int calcul(int n) {
    if (n == 0) return 0;
    return n % 10 + calcul(n / 10);
}

5. Completează valoarea returnată de cazul de bază pentru un algoritm care numără cifrele:

int nrCifre(int n) {
    if (n < 10) return ;
    return 1 + nrCifre(n / 10);
}

6. Ce returnează mister(v, 3) știind că v = {2, 5, 8}?

int mister(int v[], int n) {
    if (n == 0) return 0;
    if (v[n - 1] % 2 != 0) return mister(v, n - 1);
    return v[n - 1] + mister(v, n - 1);
}

7. Ce afișează p(4)?

void p(int n) {
    if (n > 0) { cout << "*"; p(n - 1); }
}

8. Ce returnează g(16)?

int g(int x) {
    if (x <= 1) return 1;
    return 1 + g(x / 2);
}

9. Ce afișează litere('D')?

void litere(char c) {
    if (c >= 'A') { litere(c - 1); cout << c; }
}

10. Completează codul pentru a număra valorile impare dintr-un vector:

int nrImp(int v[], int n) {
    if (n == 0) return 0;
    if (v[n - 1] % 2 != 0) return  + nrImp(v, n - 1);
    return nrImp(v, n - 1);
}

11. Ce returnează caut(10203)?

int caut(int n) {
    if (n == 0) return 0;
    if (n % 10 == 0) return 1 + caut(n / 10);
    return caut(n / 10);
}

12. Ce se va afișa pentru x(4)?

void x(int n) {
    if (n > 0) { cout << n; x(n - 1); cout << n; }
}

13. De câte ori este apelată funcția f(1) în calculul recursiv al lui f(4) (Fibonacci clasic)?

int f(int n) {
    if (n <= 1) return n;
    return f(n - 1) + f(n - 2);
}

14. Ce returnează m(462)?

int m(int n) {
    if (n < 10) return n;
    int k = m(n / 10);
    return (n % 10 > k) ? n % 10 : k;
}

15. Scrie cazul de bază pentru înmulțirea a două numere prin adunări repetate.

int inmultire(int a, int b) {
    if (  ) { return 0; }
    return a + inmultire(a, b - 1);
}

7. Evaluare Finală (15 itemi)

Bifează răspunsul corect pentru fiecare întrebare de mai jos. Când ești gata, apasă butonul pentru a primi nota și explicațiile.

1. Care este rolul Stivei (Call Stack) în recursivitate?

Să șteargă codul nefolosit. Să salveze adresa de întoarcere și variabilele locale ale apelului curent. Să transforme iterativul în recursiv.

2. Dacă o funcție recursivă nu are un Caz de Bază, ce eroare apare?

Compilation Error Stack Overflow TLE

3. Ce afișează următorul subprogram pentru apelul f(456)?

void f(int n) {
    if (n > 0) {
        f(n / 10);
        cout << n % 10;
    }
}

654 456 15

4. Pentru parcurgerea unui vector `v` de dim. `n`, pasul recursiv clasic folosește parametrul:

n+1 n-1 n%10

5. Ce calculează funcția de mai jos?

int P(int x, int y) {
    if (y == 0) return 1;
    return x * P(x, y - 1);
}

x * y x^y (x la puterea y) x + y

6. Ce returnează mist(1234) rulând codul de mai jos?

int mist(int n) {
    if (n == 0) return 0;
    if ((n % 10) % 2 == 0) {
        return 1 + mist(n / 10);
    }
    return mist(n / 10);
}

2 (numărul de cifre pare) 6 (suma cifrelor pare) 4

7. Funcția de mai jos, dacă o apelăm g('d'), va afișa:

void g(char c) {
    if (c > 'a') {
        g(c - 1);
    }
    cout << c;
}

d c b a a b c d d

8. Când subprogramul A apelează B, iar B apelează A, avem:

Recursivitate indirectă Funcții de bibliotecă Eroare de sintaxă

9. Ce se afișează pentru apelul f(2)?

void f(int n) {
    cout << "*";
    if (n > 0) {
        f(n - 1);
    }
}

** *** Nimic.

10. Cum transmitem un parametru care vrem să-și păstreze modificările în stivă?

Constant Prin referință (&) Variabilă locală

11. Expresia corectă ca bază pentru Produsul unui vector este:

if (n==0) return 0; if (n==0) return 1; if (n==0) return v[n];

12. Ce afișează apelul t(2) pe codul următor?

void t(int n) {
    if (n > 0) {
        t(n - 1);
        cout << n;
        t(n - 1);
    }
}

112 121 212

13. Cazul de bază pentru minimul dintr-un vector este:

if (n==1) return v[0]; if (n==0) return 0; if (n==1) return n;

14. Dacă șirul auto-apelurilor este prea adânc (vezi Ackermann), cum evităm Stack Overflow?

Trecem la un algoritm Iterativ (while/for) sau mărim limitarea stivei. Punem return 0 peste tot. Nu se poate evita.

15. Ce returnează F(5) folosind acest subprogram?

int F(int n) {
    if (n == 1) return 1;
    return n + F(n - 1);
}

120 15 (Suma 1+2+3+4+5) 5

1. Introducere în Recursivitate

Exemple din lumea reală

2. Mecanismul de funcționare

1. Cazul de bază - Cazul trivial (Condiția de Oprire)

2. Pasul Recursiv (Auto-apelarea)

Stiva de Apeluri (Call Stack)

3. Funcții Matematice Recursive

Factorialul unui număr ($n!$)

Varianta Iterativă (Bucle)

Varianta Recursivă

Șirul lui Fibonacci

Funcția lui Ackermann

4. Operații pe Numere (Iterativ vs Recursiv)

1. CMMDC - Prin scăderi repetate

Iterativ (while)

Recursiv

2. CMMDC - Prin împărțiri repetate (Alg. lui Euclid)

Iterativ

Recursiv

3. Suma cifrelor unui număr

Iterativ

Recursiv

4. Oglinditul unui număr

Iterativ

Recursiv

5. Construirea unui număr doar din cifrele impare

Iterativ

Recursiv

6. Combinări ($C_n^k$)

Iterativ

Recursiv

5. Recursivitatea pe Vectori

Condiții compuse și parcurgeri speciale

6. Autoevaluare (15 itemi)

7. Evaluare Finală (15 itemi)