La ricorsione è uno di quei concetti che, la prima volta, sembrano un trucco di magia: una funzione che chiama se stessa e, chissà come, arriva al risultato. Poi, a un certo punto, scatta qualcosa e diventa uno strumento naturale per descrivere problemi che hanno una struttura annidata, come cartelle dentro cartelle, commenti con risposte, menu con sottomenu. Vediamo come ragionare in modo ricorsivo senza perdersi.
L'idea in due ingredienti
Una funzione ricorsiva risolve un problema riducendolo a una versione più piccola dello stesso problema. Servono sempre due elementi:
- il caso base: una situazione abbastanza semplice da risolvere direttamente, senza altre chiamate;
- il passo ricorsivo: il modo di ricondurre il problema a uno più piccolo, avvicinandosi al caso base.
L'esempio classico è il fattoriale: il fattoriale di 5 è 5 × 4 × 3 × 2 × 1. Ma si può anche dire che il fattoriale di 5 è 5 moltiplicato per il fattoriale di 4.
def fattoriale(n):
if n <= 1: # caso base
return 1
return n * fattoriale(n - 1) # passo ricorsivo
Se manca il caso base, o se il passo ricorsivo non si avvicina a esso, la funzione si chiama all'infinito.
Cosa succede davvero
Ogni chiamata di funzione occupa uno spazio nella pila delle chiamate (call stack), dove vengono conservati i suoi parametri e le variabili locali. Quando fattoriale(4) viene chiamato, la pila cresce così:
fattoriale(4) aspetta 4 * fattoriale(3)
fattoriale(3) aspetta 3 * fattoriale(2)
fattoriale(2) aspetta 2 * fattoriale(1)
fattoriale(1) restituisce 1
Poi le chiamate si chiudono in ordine inverso: 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24. Visualizzare la pila in questo modo è il modo migliore per capire una funzione ricorsiva che non si comporta come previsto.
Il trucco mentale: fidarsi della chiamata
L'errore più comune di chi impara è cercare di seguire mentalmente tutte le chiamate fino in fondo. Con problemi complessi è impossibile. L'approccio corretto è un atto di fiducia controllata: supponi che la chiamata ricorsiva su un problema più piccolo funzioni, e chiediti solo come usarne il risultato.
Per calcolare la dimensione totale di una cartella:
from pathlib import Path
def dimensione(percorso: Path) -> int:
if percorso.is_file():
return percorso.stat().st_size # caso base
return sum(dimensione(p) for p in percorso.iterdir())
Non serve immaginare tutte le sottocartelle: basta sapere che dimensione restituisce la dimensione corretta di ciascun elemento contenuto, e che la dimensione della cartella è la loro somma. Il caso base, un file, chiude la catena.
Dove la ricorsione brilla
La ricorsione è particolarmente adatta a strutture che contengono versioni più piccole di se stesse:
- alberi: file system, documenti HTML, strutture organizzative, commenti con risposte annidate;
- dati annidati: file JSON con oggetti dentro oggetti;
- algoritmi divide et impera: merge sort, quicksort, ricerca binaria;
- esplorazione di possibilità: generare tutte le combinazioni o risolvere un rompicapo provando e tornando indietro (backtracking).
In tutti questi casi la versione iterativa è possibile, ma di solito richiede di gestire a mano una pila, ed è più lunga e meno leggibile.
Il problema delle chiamate ripetute
Ecco la versione ricorsiva più ingenua della successione di Fibonacci, in cui ogni numero è la somma dei due precedenti:
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
È elegante ma lentissima: fib(5) calcola fib(3) due volte, fib(2) tre volte, e il numero di chiamate cresce in modo esponenziale. La soluzione è la memoizzazione, cioè ricordare i risultati già calcolati:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
Con una sola riga in più, ogni valore viene calcolato una volta e la complessità diventa lineare.
Limiti pratici
In Python la profondità della ricorsione è limitata: oltre una certa soglia, di default intorno al migliaio di chiamate, si ottiene un RecursionError. Python, inoltre, non applica l'ottimizzazione delle chiamate in coda presente in altri linguaggi. Per questo:
| Situazione | Scelta consigliata |
|---|---|
| Struttura ad albero di profondità moderata | Ricorsione |
| Elaborazione lineare di molti elementi | Ciclo |
| Profondità potenzialmente molto grande | Versione iterativa con una pila esplicita |
| Sottoproblemi ripetuti | Ricorsione con memoizzazione o programmazione dinamica |
Aumentare il limite con sys.setrecursionlimit è possibile, ma è più un rimedio temporaneo che una soluzione.
In sintesi
- Una funzione ricorsiva ha sempre un caso base e un passo che si avvicina a esso.
- Ogni chiamata occupa spazio nella pila: visualizzarla aiuta a capire il comportamento.
- Ragiona fidandoti della chiamata su un problema più piccolo, invece di seguirle tutte.
- La ricorsione è ideale per alberi e dati annidati; la memoizzazione evita calcoli ripetuti.
- In Python la profondità è limitata: per elaborazioni lunghe preferisci un ciclo.
