memoizzazione

La memoizzazione è una tecnica di programmazione che consiste nel salvare in memoria i valori restituiti da una funzione in modo da averli a disposizione per un riutilizzo successivo senza doverli ricalcolare. Memoizzazione, che significa letteralmente "mettere in memoria" è una tecnica caratteristica della programmazione dinamica. Spesso questo termine viene confuso con "memorizzazione" che, sebbene descriva lo stesso procedimento, ha un significato più ampio. Una funzione può essere "memoizzata" soltanto se soddisfa la trasparenza referenziale, cioè se non ha effetti collaterali e restituisce sempre lo stesso valore quando riceve in input gli stessi parametri. Le operazioni che non soddisfano questa condizione, ma i cui valori restituiti hanno una piccola probabilità di cambiare, possono ancora essere duplicate ("cached", dal francese caché) usando tecniche più complesse. In generale, i risultati memoizzati non perdono di validità nel tempo, mentre, al contrario, quelli duplicati la perdono. Nei linguaggi di programmazione funzionale è possibile costruire una funzione di livello superiore memoize che, a sua volta, creerà automaticamente funzioni memoizzate per ogni funzione dotata di trasparenza referenziale. Al contrario, invece, nei linguaggi privi di funzioni di ordine superiore, la memoizzazione deve essere implementata separatamente per ciascuna funzione che ne deve beneficiare. La tecnica è anche spesso utilizzata nell'approccio top-down in programmazione dinamica.