Ricorsione: risolvere un problema con versioni più piccole di sé stesso — Tecnologia, 14–17 anni
La ricorsione permette a un programma di ripetere un’idea richiamando sé stesso su un caso più piccolo. Deve anche sapere quando fermarsi, altrimenti il processo non finisce mai.
Una versione più piccola dello stesso problema
Immagina di aprire scatole una dentro l’altra: dentro ciascuna ce n’è una più piccola, fino all’ultima, vuota. Un programma ricorsivo fa qualcosa di simile, risolvendo ogni volta una versione più piccola del compito. Serve un caso base con una risposta diretta.
Perché usare la ricorsione?
Alcuni problemi hanno già una forma ramificata o annidata: le cartelle contengono cartelle, le pagine rimandano ad altre pagine e gli alberi genealogici si dividono in rami. La ricorsione segue questa forma e può essere più chiara di un lungo elenco di casi speciali.
Esempio svolto: il fattoriale
Per calcolare 4!, definiamo 1! uguale a 1 e usiamo n! = n × (n−1)!. Quindi 4! diventa 4 × 3!, poi 4 × 3 × 2!, infine 4 × 3 × 2 × 1!, cioè 24. Il caso base 1! ferma la catena.
Il punto di arresto mancante
Un errore comune è scrivere il richiamo a sé stesso e dimenticare il caso base, oppure cambiare così poco il valore da non raggiungerlo mai. È comprensibile, perché il passaggio ripetuto sembra l’idea principale. Il risultato è spesso uno stack overflow: troppe chiamate rimangono aperte.
Dove compare
I gestori dei file possono cercare dentro cartelle contenute in altre cartelle, mentre i programmi di disegno possono creare forme ramificate come alberi o fiocchi di neve. Questi compiti hanno una struttura annidata, quindi la ricorsione li descrive bene. Non è sempre la più veloce: un metodo iterativo può usare meno memoria.
Continua a esplorare
Altre lingue
Caricamento di MyLeoNes™…