# Recursivitate: funcții care se autoapelează

> Pagina: https://bacalaurescu.ro/informatica/lectii/recursivitate/functii-recursive
> Markdown: https://bacalaurescu.ro/informatica/lectii/recursivitate/functii-recursive.md
> Sursa: Bacalaurescu (bacalaurescu.ro), conținut gratuit pentru BAC 2027.

Materia: [Informatică](https://bacalaurescu.ro/informatica)

Capitolul: [Recursivitate](https://bacalaurescu.ro/informatica/lectii/recursivitate)
Actualizat: 2026-11-01

Mecanismul recursivității, cazul de bază, exemple clasice și urmărirea apelurilor.

## Pe scurt pentru BAC

- O funcție este recursivă dacă se apelează pe ea însăși, ca factorialul definit prin $n! = n \cdot (n-1)!$ și $0! = 1$.
- Suma cifrelor recursivă întoarce `n % 10 + sc(n / 10)`, iar cazul de bază `n == 0` întoarce 0.
- Algoritmul lui Euclid recursiv întoarce `a` când `b == 0`, altfel apelează `cmmdc(b, a % b)`.
- Ca să urmărești un apel, scrii fiecare apel pe un rând, cobori până la cazul de bază, apoi urci înlocuind apelurile cu valorile returnate.
- Fără caz de bază sau cu un autoapel care nu micșorează problema, funcția se apelează la infinit (stack overflow).

## Ce este recursivitatea

O funcție este **recursivă** dacă se apelează pe ea însăși. Orice funcție recursivă corectă are:

1. **cazul de bază**: condiția de oprire, fără autoapel;
2. **cazul general**: autoapelul pe o problemă MAI MICĂ.

## Exemplul fundamental: factorialul

$$n! = n \cdot (n-1)! \qquad 0! = 1$$

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

Urmărirea pentru `fact(4)`: $4 \cdot fact(3) = 4 \cdot 3 \cdot fact(2) = 4 \cdot 3 \cdot 2 \cdot fact(1) = 4 \cdot 3 \cdot 2 \cdot 1 \cdot fact(0) = 24$.

## Alte exemple clasice

**Suma cifrelor:**

```cpp
int sc(int n) {
    if (n == 0) return 0;
    return n % 10 + sc(n / 10);
}
```

`sc(275)` = 5 + `sc(27)` = 5 + 7 + `sc(2)` = 5 + 7 + 2 + `sc(0)` = 14.

**Cel mai mare divizor comun (Euclid):**

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

`cmmdc(24, 36)` = `cmmdc(36, 24)` = `cmmdc(24, 12)` = `cmmdc(12, 0)` = 12.

## Cum urmărești un apel la BAC

1. Scrie fiecare apel pe un rând, cu argumentele lui.
2. Coboară până la cazul de bază.
3. Urcă înapoi înlocuind fiecare apel cu valoarea returnată.

> [!ATENTIE]
> Fără caz de bază (sau cu autoapel care NU micșorează problema), funcția se apelează la infinit: stack overflow. La subiectele de tip "ce afișează", verifică întâi condiția de oprire.

> [!RETINE]
> Orice funcție recursivă are un caz de bază (oprire, fără autoapel) și un caz general (autoapel pe o problemă mai mică). Valori de verificare: `fact(0) = 1`, `sc(275) = 14`, `cmmdc(24, 36) = 12`.

## Greșeli frecvente

1. Ordinea contează: `return n * fact(n-1)` înmulțește DUPĂ întoarcerea din apel.
2. La afișări recursive, instrucțiunile de DINAINTE de autoapel se execută la coborâre, cele de DUPĂ la întoarcere: de aici apar afișările "inversate".
3. `fact(0)` este 1, nu 0.