Ce este recursiunea?

Question

Accepted Answer

**Recursiunea** este atunci când o funcție se apelează pe sine pentru a rezolva o versiune mai mică a aceleiași probleme. Fiecare recursiune are nevoie de un **caz de bază** care o oprește și de un **caz recursiv** care avansează spre bază.

## Ideea

Împarte o problemă în subprobleme mai mici și identice. Fiecare apel împinge un frame pe **stiva de apeluri** (call stack); returnurile le scot.

## Exemplu

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## Urmărire

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## Complexitate

Aici **O(n)** timp și **O(n)** spațiu de stivă (un frame pe apel).

## Capcane

- **Caz de bază lipsă** -> recursiune infinită -> overflow de stivă.
- Recursiunea profundă poate epuiza stiva; unele limbaje nu au optimizare tail-call.
- Recalcularea subproblemelor suprapuse poate duce la timp exponențial (repară cu memoizare).

## De ce conteaza

Recursiunea exprimă în mod natural probleme autosimilare — copaci, grafuri, divide and conquer — mult mai curat decât buclele.

Este modelul mental din spatele merge sort, backtracking și programării dinamice.

Înțelegerea stivei de apeluri te face și mai bun la depanare și raționament despre memorie.