Ricorsione — Informatica, 11–13
La ricorsione risolve un problema grande applicando la stessa regola a una versione più piccola, fino a raggiungere un punto semplice in cui fermarsi.
Una regola che richiama se stessa
Nella ricorsione, un’istruzione risolve una parte e poi chiede alla stessa istruzione di risolvere una parte più piccola. Deve anche sapere quando fermarsi: questo è il caso base. Il disegno di un ramo mostra l’idea: ogni ramo si divide in rami più piccoli, ma il rametto più piccolo non si divide ancora.
Perché usare la ricorsione?
Alcune cose sono formate da copie più piccole dello stesso tipo: le cartelle contengono cartelle, gli alberi genealogici si dividono in rami e le mappe contengono regioni dentro altre regioni. Una lunga lista di istruzioni separate sarebbe difficile da scrivere e modificare. La ricorsione serve a descrivere queste strutture annidate con una regola chiara invece di ripetere codice simile.
Contare alla rovescia
Usa una regola chiamata conta(n): se n è 0, fermati; altrimenti mostra n e richiama conta(n−1). Inizia con conta(3). Mostra 3, poi richiama conta(2), che mostra 2 e richiama conta(1). Questa mostra 1 e richiama conta(0); il caso base ferma tutto, quindi il risultato finale è 3, 2, 1.
Dimenticare il punto di arresto
Una regola ricorsiva può sembrare elegante, quindi è facile lasciarla richiamare se stessa senza controllare un caso base. È un errore comprensibile: sembra che i compiti più piccoli prima o poi finiscano. Senza un punto di arresto, però, il valore può non arrivare mai alla fine e il computer continua a creare chiamate incomplete finché esaurisce lo spazio o segnala un errore.
Cartelle e forme ramificate
Un programma per i file può cercare in una cartella e poi in ogni cartella contenuta, anche quando sono annidate in profondità. I programmi di disegno usano la ricorsione anche per piante ramificate, forme simili a fiocchi di neve e percorsi nei labirinti. Non ti serve la ricorsione per ogni azione ripetuta; è più utile quando ogni parte contiene parti più piccole con la stessa struttura.
Continua a esplorare
Altre lingue
Caricamento di MyLeoNes™…