C++
Recursion en C ++

Uso de la recursión de la cola y la recursión del estilo de Fibonnaci para resolver la secuencia de Fibonnaci

La forma más simple y más obvia de usar la recursión para obtener el enésimo término de la secuencia de Fibonnaci es esta

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);
}

Sin embargo, este algoritmo no se escala para términos más altos: para n más grande y más grande, la cantidad de llamadas a funciones que necesita realizar crece exponencialmente. Esto puede ser reemplazado con una simple recursión de cola.

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);
}

Cada llamada a la función ahora calcula inmediatamente el siguiente término en la secuencia de Fibonnaci, por lo que el número de llamadas a función se escala linealmente con n .

Recursion con memoizacion.

Las funciones recursivas pueden ser bastante caras. Si son funciones puras (funciones que siempre devuelven el mismo valor cuando se las llama con los mismos argumentos, y que no dependen ni modifican el estado externo), pueden hacerse considerablemente más rápido a expensas de la memoria almacenando los valores ya calculados.

La siguiente es una implementación de la secuencia de Fibonacci con memoización:

#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;
  }
}

Tenga en cuenta que a pesar de usar la fórmula de recursión simple, en la primera llamada esta función es $ O (n) $. En llamadas subsiguientes con el mismo valor, es por supuesto $ O (1) $.

Tenga en cuenta, sin embargo, que esta implementación no es reentrante. Además, no permite deshacerse de los valores almacenados. Una implementación alternativa sería permitir que el mapa se pase como argumento adicional:

#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;
  }
}

Para esta versión, se requiere que la persona que llama mantenga el mapa con los valores almacenados. Esto tiene la ventaja de que la función ahora está reentrada y que la persona que llama puede eliminar valores que ya no son necesarios, lo que ahorra memoria. Tiene la desventaja de que rompe la encapsulación; la persona que llama puede cambiar la salida al rellenar el mapa con valores incorrectos.