Un uso poco accorto della ricorsione può comportare seri problemi di efficienza dovuti alla ripetizione di calcoli già effettuati
Approccio top-down: la soluzione di un problema viene calcolata a partire dalle soluzioni di problemi più piccoli
Problema: può capitare che uno stesso problema venga risolto un numero esponenziale di volte
Soluzione: programmazione dinamica
L'idea: si risolvono tutte le istanze richieste dal problema partendo dalle più "piccole" e si memorizzano i risultati, in modo che possano essere riutilizzati mano a mano che si risolvono istanze di dimensione superiore
Si consideri un algoritmo ricorsivo descritto dalle procedure $P_1,...,P_m$ dove $P_1$ è la procedura principale
$[P_k, x]$ indica la chiamata di $P_k$ con input $x$
$[P_k,x]$ dipende da $[P_s,y]$ se la chiamata di $P_k$ con input $x$ implica una chiamata $P_s$ con input $y$, anche non direttamente
il risultato dell'algoritmo sull'input z è calcolato dalla chiamata $[P_1, z]$
Consideriamo l'insieme di dipendenza
$D[P_1,z] = \{[P_s,y] \ se \ [P_s,y]$ dipende da $[P_k,y]\}$
ad esempio $D[Fib, 4]=\{[Fib, 3], [Fib, 2], [Fib,1], [Fib, 0]\}$
indichiamo con < l'ordine (parziale) su $D[P_1, z]$ definito da
$$ \forall [P_k, x], [P_s, y] \in D[P_1, z], \ \ \ [P_k, x]<[P_s, y] \ \lrarr \ [P_s, y] \text{ dipende da }[P_k, x] $$
definiamo un ordine totale $\prec$ compatibile con $<$
Osservazioni: