Ricorsione¶
Parte 5 del corso, volume 5 delle dispense. La ricorsione: algoritmi ricorsivi classici, equazioni di ricorrenza, il Master theorem, algoritmi ricorsivi (somma di un array, merge sort, ricerca binaria, sotto-array di somma massima) e il confronto fra versioni ricorsive e iterative.
-
14. Ricorsione
Algoritmi ricorsivi · Albero delle chiamate ricorsive e call stack · Correttezza degli algoritmi ricorsivi · Fattoriale · …
-
15. Equazioni di ricorrenza
Equazioni di ricorrenza · Il metodo di espansione · Il metodo di sostituzione · Il metodo dell'albero di ricorsione · …
-
16. Il Master theorem
Ricorrenze in forma standard · Il Master theorem · Applicare il Master theorem · Quando il Master theorem non si applica · …
-
17. Algoritmi ricorsivi
La somma degli elementi di un array · Merge Sort · Ricerca binaria ricorsiva · Il problema del sotto-array di somma massima · …
-
18. Algoritmi ricorsivi e iterativi a confronto
Ricorsione e iterazione · Confronto in sintesi · Il divide et impera dà il guadagno, non la ricorsione in sé · Quando i sottoproblemi si sovrappongono · …