Cos'è la ricorsione (con esempi)

La ricorsione è uno di quei concetti che all'inizio sembra magia nera e poi, una volta capito, diventa uno strumento elegante. Si tratta di una funzione che chiama se stessa: detta così suona strana, ma ha una logica precisa.

In questo articolo ti spiego cos'è la ricorsione con esempi semplici, ti mostro come evitare i loop infiniti e quando conviene usarla.

Cos'è la ricorsione in parole semplici

La ricorsione è una tecnica di programmazione in cui una funzione risolve un problema chiamando se stessa su una versione più piccola dello stesso problema, fino a raggiungere un caso così semplice da poter essere risolto direttamente. Quel caso semplice si chiama "caso base".

Immagina delle matrioske russe. Per aprirle tutte, apri quella più grande, trovi una matrioska più piccola e ripeti lo stesso gesto, finché non arrivi a quella minuscola che non si apre più. Quel momento è il caso base.

I due ingredienti di ogni ricorsione

Ogni funzione ricorsiva ha bisogno di due cose, e devono esserci entrambe:

• Il caso base: la condizione che ferma la ricorsione. Senza, la funzione si chiamerebbe all'infinito.
• Il caso ricorsivo: la chiamata a se stessa su un problema più piccolo, che si avvicina sempre più al caso base.

Se dimentichi il caso base ottieni un loop infinito che fa crashare il programma. È l'errore numero uno dei principianti con la ricorsione.

Esempio classico: il fattoriale

Il fattoriale di un numero n (scritto n!) è il prodotto di tutti i numeri da 1 a n. Per esempio 4! = 4 × 3 × 2 × 1 = 24. Si presta benissimo alla ricorsione, perché n! = n × (n-1)!.

def fattoriale(n):
    if n <= 1:               # caso base
        return 1
    return n * fattoriale(n - 1)  # caso ricorsivo

print(fattoriale(4))  # 24

Segui il ragionamento: fattoriale(4) chiama fattoriale(3), che chiama fattoriale(2), che chiama fattoriale(1). Quest'ultima è il caso base e restituisce 1, poi i risultati "risalgono" moltiplicandosi.

Un secondo esempio: Fibonacci

La successione di Fibonacci è un altro classico: ogni numero è la somma dei due precedenti (0, 1, 1, 2, 3, 5, 8...).

def fibonacci(n):
    if n < 2:                # casi base: 0 e 1
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(7))  # 13

Qui ci sono due chiamate ricorsive, una struttura che genera un "albero" di chiamate.

Ricorsione vs iterazione

Quasi tutto ciò che fai con la ricorsione puoi farlo anche con un ciclo (iterazione). Quando scegliere l'una o l'altra?

• La ricorsione brilla con problemi naturalmente "annidati": alberi, cartelle dentro cartelle, strutture gerarchiche.
• L'iterazione è spesso più efficiente in memoria, perché non accumula chiamate.

Attenzione: ogni chiamata ricorsiva occupa spazio nello stack. Se vai troppo in profondità rischi un errore di "stack overflow". Inoltre la versione ricorsiva di Fibonacci qui sopra è lenta per numeri grandi, perché ricalcola gli stessi valori più volte: un caso in cui capire la complessità computazionale ti salva.

Dove la incontri davvero

La ricorsione non è solo un esercizio da manuale. La trovi quando:

• esplori l'albero di file e cartelle di un disco;
• navighi strutture come i tipi di dati ad albero;
• elabori dati gerarchici come il JSON annidato.

In sintesi

La ricorsione è una funzione che chiama se stessa per scomporre un problema in versioni più piccole, fermandosi al caso base. Ricorda sempre i due ingredienti: caso base e caso ricorsivo. Usata bene, rende elegante la soluzione di problemi che con i cicli sarebbero contorti.

La ricorsione si capisce davvero solo scrivendola e tracciandola passo dopo passo. Se vuoi farlo con esercizi guidati, dai un'occhiata ai corsi di CodeGrind: la teoria diventa pratica fin da subito.