Ricorsione
CORDA – Informatica
A. Ferrari
Testi da
Alessandro Bugatti
Olimpiadi di Informatica
Guida alle sezioni territoriali
Campi di applicazione
 problemi di tipo “divide et impera”
 la soluzione di un problema si ottiene suddividendo il
problema in due o più parti che lo compongono, le quali
vengono risolte separatamente e poi si rimette insieme
quanto ottenuto per avere la soluzione al problema di
partenza
 problemi dove è necessario generare tutti i casi possibili
rispetto ad alcune scelte che si possono fare e scegliere il
caso ottimo per il problema in questione
 problemi di programmazione dinamica, nei quali la
soluzione iterativa è applicabile, ma la soluzione ricorsiva è
più semplice e/o elegante
Funzioni ricorsive
 la funzione richiama se stessa su una versione più piccola
dello stesso problema
 c’è sempre una condizione di cui si conosce la soluzione
e che fa terminare la ricorsione
Se una delle precedenti caratteristiche non venisse
rispettata si entrerebbe in una ricorsione infinita
Algoritmi ricorsivi
 la maggior parte dei problemi ha una formulazione
iterativa diretta
 esiste un insieme di problemi in cui la formulazione
ricorsiva risulta più semplice e elegante da esprimere e
da implementare
… problemi della ricorsione
 Un problema che nella pratica limita l’utilizzo della
ricorsione si ha quando le chiamate ricorsive non
crescono in modo lineare, ma in maniera molto più
veloce
 Esempio: numero di Fibonacci
Fibonacci
(funzione elegante ma inefficiente)
Programmazione dinamica
 Tecnica di progettazione di algoritmi basata su
 divisione del problema in sottoproblemi
 utilizzo di sottostrutture ottimali
 Sottostruttura ottimale
 la soluzione ottimale al sottoproblema può essere utilizzata
per trovare la soluzione ottimale dell'intero problema
Fibonacci
(programmazione dinamica)
il vettore poteva non essere utilizzato, perché ad ogni passo
servono solo i due valori precedenti e quindi sarebbero bastate
due variabili
Fibonacci ricorsivo
(programmazione dinamica)
E’ necessario inizializzare Fibonacci con tutti i suoi elementi a -1 ,
Fibonacci[0]=0 e Fibonacci[1]=1
Scarica

pptx - Alberto Ferrari