Cos'è la ricorsione?

Question

Accepted Answer

**Ricorsione** è quando una funzione chiama se stessa per risolvere una versione più piccola dello stesso problema. Ogni ricorsione necessita di un **caso base** che la ferma e di un **caso ricorsivo** che si avvicina al base.

## L'idea

Scomponi un problema in sottoproblemi identici più piccoli. Ogni chiamata inserisce un frame nello **stack di chiamate**; i ritorni li estraggono.

## Esempio

```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
```

## Traccia

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

## Complessità

Qui **O(n)** tempo e **O(n)** spazio stack (un frame per ogni chiamata).

## Insidie

- **Caso base mancante** -> ricorsione infinita -> stack overflow.
- La ricorsione profonda può esaurire lo stack; alcuni linguaggi mancano di tail-call optimization.
- Ricalcolare sottoproblemi sovrapposti può portare a tempo esponenziale (correggi con memoization).

## Perché è importante

La ricorsione esprime naturalmente problemi autosimili — alberi, grafi, divide and conquer — molto più chiaramente rispetto ai cicli.

È il modello mentale dietro merge sort, backtracking e programmazione dinamica.

Comprendere lo stack di chiamate ti rende anche più bravo nel debugging e nel ragionare sulla memoria.