C++ Ricorsione con memoization


Esempio

Le funzioni ricorsive possono diventare piuttosto costose. Se sono funzioni pure (funzioni che restituiscono sempre lo stesso valore quando vengono richiamate con gli stessi argomenti e che non dipendono né modificano lo stato esterno), possono essere rese notevolmente più veloci a scapito della memoria memorizzando i valori già calcolati.

Quanto segue è un'implementazione della sequenza di Fibonacci con la memoizzazione:

#include <map>

int fibonacci(int n)
{
  static std::map<int, int> values;
  if (n==0 || n==1)
    return n;
  std::map<int,int>::iterator iter = values.find(n);
  if (iter == values.end())
  {
    return values[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  else
  {
    return iter->second;
  }
}

Si noti che nonostante l'uso della semplice formula di ricorsione, in prima chiamata questa funzione è $ O (n) $. Sulle chiamate successive con lo stesso valore, è ovviamente $ O (1) $.

Si noti tuttavia che questa implementazione non è rientranti. Inoltre, non consente di eliminare i valori memorizzati. Un'implementazione alternativa sarebbe quella di consentire alla mappa di essere passata come argomento aggiuntivo:

#include <map>

int fibonacci(int n, std::map<int, int> values)
{
  if (n==0 || n==1)
    return n;
  std::map<int,int>::iterator iter = values.find(n);
  if (iter == values.end())
  {
    return values[n] = fibonacci(n-1) + fibonacci(n-2);
  }
  else
  {
    return iter->second;
  }
}

Per questa versione, il chiamante è tenuto a mantenere la mappa con i valori memorizzati. Questo ha il vantaggio che la funzione è ora rientrante e che il chiamante può rimuovere i valori che non sono più necessari, risparmiando memoria. Ha lo svantaggio che rompe l'incapsulamento; il chiamante può modificare l'output popolando la mappa con valori errati.