Recursivitate

Ce este recursivitatea

O functie este recursiva daca se apeleaza pe ea insasi. Orice functie recursiva are:

1. Cazul de baza — conditia de oprire (fara ea → bucla infinita)
2. Apelul recursiv — apelul cu un subproblema mai simpla

---

Exemplu: factorial

long long fact(int n) {
    if (n == 0) return 1;        // caz de baza
    return n * fact(n - 1);      // apel recursiv
}

Trasarea pentru n = 4:

fact(4) = 4 * fact(3)
              = 3 * fact(2)
                    = 2 * fact(1)
                          = 1 * fact(0)
                                = 1

Rezultat: 4 * 3 * 2 * 1 * 1 = 24

---

Exemplu: Fibonacci

int fib(int n) {
    if (n <= 1) return n;          // fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2);
}

Varianta recursiva e ineficienta (O(2ⁿ)) — pentru n mare foloseste iterativ sau memoizare.

---

Exemplu: CMMDC (Algoritm Euclid)

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

---

Exemplu: putere (exponentiere rapida)

long long putere(long long baza, int exp) {
    if (exp == 0) return 1;
    if (exp % 2 == 0) {
        long long jum = putere(baza, exp / 2);
        return jum * jum;
    }
    return baza * putere(baza, exp - 1);
}

---

Exemplu: suma cifrelor

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

---

Recursivitate pe tablouri

// suma elementelor v[st..dr]
int suma(int v[], int st, int dr) {
    if (st == dr) return v[st];
    int mij = (st + dr) / 2;
    return suma(v, st, mij) + suma(v, mij + 1, dr);
}

---

Stiva de apeluri

La fiecare apel recursiv, programul salveaza pe stiva valorile variabilelor locale si adresa de retur. Prea multe apeluri → stack overflow.

Adancimea maxima practica: cateva mii de apeluri recursive.

---

Recursiv vs. iterativ

	Recursiv	Iterativ
Cod	Mai scurt, elegant	Mai lung, dar mai eficient
Memorie	Stiva (overhead)	Constanta
Viteza	Poate fi mai lent	De obicei mai rapid
Cand folosim	Backtracking, D&I, structuri arborescente	Calcule simple

---

La examen

• Identifica cazul de baza primul — scrie-l pe primul if
• Verifica daca functia converge: fiecare apel recursiv trebuie sa fie pe o subproblema strict mai mica
• La trasare: deseneaza arborele de apeluri sau urmareste stiva de sus in jos