C++
Ricorsione in C ++

Usando la ricorsione della coda e la ricorsione in stile Fibonaci per risolvere la sequenza di Fibonacci

Il modo semplice e più ovvio di usare la ricorsione per ottenere l'ennesimo termine della sequenza di Fibonnaci è questo

int get_term_fib(int n)
{
  if (n == 0)
    return 0;
  if (n == 1)
    return 1;
  return get_term_fib(n - 1) + get_term_fib(n - 2);
}

Tuttavia, questo algoritmo non è scalabile per termini più elevati: per n più grandi, il numero di chiamate di funzione che è necessario fare cresce in modo esponenziale. Questo può essere sostituito con una semplice ricorsione della coda.

int get_term_fib(int n, int prev = 0, int curr = 1)
{
  if (n == 0)
    return prev;
  if (n == 1)
    return curr;
  return get_term_fib(n - 1, curr, prev + curr);
}

Ogni chiamata alla funzione calcola immediatamente il termine successivo nella sequenza di Fibonnaci, quindi il numero di chiamate di funzione scala linearmente con n .

Ricorsione con memoization

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.