La Ricorsione Spiegata: Quando Usarla e Quando Evitarla

Una funzione che richiama se stessa ha una profondità massima, ed è più piccola di quanto la maggior parte delle persone si aspetti: 1.000 chiamate in CPython di default, circa 10.000-15.000 in Node e nei motori dei browser, a seconda di quanto pesa ogni frame. Superarla non significa che il programma rallenta: crasha. Python solleva RecursionError: maximum recursion depth exceeded; JavaScript solleva RangeError: Maximum call stack size exceeded.

Entrambi gli errori hanno la stessa causa, e una volta vista capisci subito quando la ricorsione è lo strumento giusto e quando diventa un rischio.

Cosa fa davvero una funzione ricorsiva allo stack

Ogni chiamata a funzione mette un frame sullo stack: gli argomenti, le variabili locali, l’indirizzo a cui tornare. Una chiamata normale ritorna e il suo frame viene rimosso. Una chiamata ricorsiva non può ancora tornare, perché è in attesa della chiamata che ha appena fatto, quindi ogni frame resta sullo stack finché quello sotto non finisce.

1
2
3
4

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

factorial(4) costruisce quattro frame sullo stack prima che uno solo produca un valore:

1
2
3
4

factorial(4) -> 4 * factorial(3)
                     factorial(3) -> 3 * factorial(2)
                                          factorial(2) -> 2 * factorial(1)
                                                               factorial(1) -> 1   # caso base, lo stack smette di crescere

Solo quando factorial(1) ritorna 1 lo stack si svuota: 2 * 1, poi 3 * 2, poi 4 * 6, risultato 24.

A far funzionare tutto questo sono due pezzi. Il caso base (n <= 1) ferma la ricorsione. Il caso ricorsivo richiama la funzione con un input che si muove verso il caso base. Togline uno e la funzione non si ferma più: in Python arrivi a RecursionError in meno di mille chiamate, in un linguaggio senza limite il processo muore per stack overflow.

Quando la ricorsione è lo strumento giusto: dati annidati

La ricorsione si guadagna il suo posto quando i dati sono annidati a una profondità che non conosci in anticipo: un albero, un filesystem, un JSON annidato a piacere. Un ciclo su quel tipo di dati ha bisogno di uno stack gestito a mano. La ricorsione te ne dà uno gratis, perché lo stack delle chiamate è lo stack di cui avevi bisogno.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

flatten([1, [2, 3, [4, [5, 6]], 7], 8])
# [1, 2, 3, 4, 5, 6, 7, 8]

Ogni chiamata a flatten gestisce un livello. Quando incontra una lista annidata, la passa a una nuova chiamata, e lo stack ricorda dove riprendere nella lista esterna una volta finita quella interna. La versione iterativa dovrebbe tenere traccia di quella posizione da sola.

Camminare su un albero di directory ha la stessa forma:

1
2
3
4
5
6

from pathlib import Path

def total_size(path: Path) -> int:
    if path.is_file():
        return path.stat().st_size
    return sum(total_size(child) for child in path.iterdir())

total_size non distingue tra una directory profonda un livello o dieci. Ogni chiamata gestisce il proprio path.

Quando la ricorsione è lo strumento sbagliato: input piatto e lungo

Sommare una lista piatta è il caso opposto. Non c’è annidamento, quindi la ricorsione non porta nessun vantaggio, solo rischio di stack.

1
2
3
4

def sum_recursive(nums):
    if not nums:
        return 0
    return nums[0] + sum_recursive(nums[1:])

Funziona su input piccoli e crolla su input reali:

1
2
3
4

>>> sum_recursive(list(range(2000)))
Traceback (most recent call last):
  ...
RecursionError: maximum recursion depth exceeded

Duemila elementi, un frame per elemento, il doppio del limite di default. La versione a ciclo usa un solo frame indipendentemente dalla lunghezza della lista:

1
2
3
4
5

def sum_iterative(nums):
    total = 0
    for n in nums:
        total += n
    return total

sum_iterative(list(range(1_000_000))) ritorna all’istante. In termini di notazione Big O entrambe le versioni sono O(n) in tempo, ma quella ricorsiva costa anche O(n) in spazio sullo stack, e quello spazio è limitato a circa mille frame.

La tail-call optimization risolve la ricorsione profonda in Python o JavaScript?

No. In sum_recursive, l’ultima cosa che accade è l’addizione, non la chiamata ricorsiva, quindi ogni frame deve restare vivo per ricevere un risultato e aggiungerlo. Puoi riscriverla in modo che la chiamata ricorsiva sia proprio l’ultima operazione, portando con sé il totale parziale come argomento:

1
2
3
4

def sum_tail(nums, acc=0):
    if not nums:
        return acc
    return sum_tail(nums[1:], acc + nums[0])

In un linguaggio con tail-call optimization, il compilatore vede che non serve più nulla nel frame del chiamante dopo la chiamata e riusa quel frame invece di impilarne uno nuovo. La ricorsione diventa un ciclo sotto il cofano.

CPython non lo fa, per scelta di design: i core developer l’hanno respinta perché renderebbe i traceback più difficili da leggere. sum_tail colpisce comunque il limite su una lista di 2.000 elementi. Lo spec ES2015 di JavaScript include le proper tail calls, ma V8 (Chrome, Node.js) e SpiderMonkey (Firefox) non le hanno mai implementate; solo JavaScriptCore di Safari lo fa.

Quindi la regola è la stessa in entrambi i linguaggi. Se la dimensione dell’input decide quanto profonda arriva la ricorsione, non contare sul motore per salvarti. Convertila in un ciclo, oppure limita la profondità.

Come la memoization risolve la ricorsione lenta

Alcune funzioni ricorsive non si avvicinano nemmeno al limite di profondità. Il loro problema è che calcolano la stessa cosa più volte. Il Fibonacci ricorsivo ingenuo è il caso da manuale:

1
2
3
4

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

fib(5) chiama fib(4) e fib(3), e fib(4) chiama di nuovo fib(3). Quella duplicazione si accumula a ogni livello, quindi il numero di chiamate cresce in modo esponenziale con n (di un fattore di circa 1,6 per passo, di solito scritto come limite superiore O(2^n)). In CPython, fib(30) richiede già circa un decimo di secondo e fib(40) oltre dieci secondi.

La soluzione lascia la ricorsione intatta e mette in cache i risultati, così ogni input distinto viene calcolato una sola volta:

1
2
3
4
5
6
7

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

lru_cache è un decoratore. Avvolge fib_memo, e quando un argomento si ripete restituisce il risultato salvato invece di eseguire di nuovo il corpo della funzione. fib_memo(40) ritorna all’istante.

La profondità non cambia: fib_memo(40) ha comunque bisogno di circa 40 frame sullo stack. Cambia il numero di chiamate, che passa da esponenziale a lineare. Paghi O(n) di memoria per la cache e ottieni O(n) di tempo invece che esponenziale.

Ricorsione o iterazione: quale usare

Un caso merita più di una riga di tabella. Se la profondità della ricorsione è controllata da un input di cui non ti fidi, è un vettore di denial-of-service. Un parser ricorsivo che scende di un livello per ogni parentesi annidata in un testo fornito dall’utente può essere fatto crashare da chiunque invii qualche migliaio di caratteri [. Limita la profondità in modo esplicito, oppure non usare la ricorsione.

Come convertire una funzione ricorsiva in un ciclo

Il sostituto diretto della ricorsione su un albero è uno stack esplicito: una list su cui fai push e pop a mano, guidata da un ciclo while. Ecco flatten riscritta così:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def flatten_iterative(nested):
    result = []
    stack = [iter(nested)]
    while stack:
        for item in stack[-1]:
            if isinstance(item, list):
                stack.append(iter(item))
                break
            result.append(item)
        else:
            stack.pop()
    return result

Produce lo stesso output con un solo frame sullo stack, indipendentemente da quanto in profondità arriva l’input. Il costo è la gestione esplicita, visibile nel codice: lo stack di iteratori è esattamente ciò che lo stack delle chiamate teneva traccia per te.

La prossima volta che scrivi una funzione ricorsiva, chiediti quanto in profondità può arrivare. Se la risposta è piccola e nota (un file di configurazione, un albero di componenti UI, un parse tree per una tua grammatica), tieni la ricorsione. Se la risposta è “quello che dice l’input”, scrivi il ciclo.

Articoli correlati

• Notazione Big O Spiegata con Esempi di Codice
• Git Bisect: Trovare il Commit che ha Introdotto un Bug