Esquema recursivo con almacen.

Preparando la docencia de DAA me encontre un esquema de programación muy interesante e intuitivo, el esquema recursivo con almacen. Cuando ejecutamos una función recursiva, en ocasiones, dicha función vuelve a resolver problemas para los cuales ya ha calculado la solución. Por ejemplo, en el caso de la serie de Fibonacci:

La funcion recursiva que resuelve esta formula es la siguiente (en C/C++)

int fiboR(int n)
{
   int resultado;

   if(n == 0 || n == 1)
      resultado = 1;
   else
      resultado = f(n-1) + f(n-2);
   
   return resultado;
}

Si realizamos el árbol de llamadas recursivas para f(6) podemos observar que existen subproblemas (llamadas) que se vuelven a resolver (desarrollar).


La idea es crear un vector donde guardamos las soluciones de las llamadas ya realizadas y antes de volver a realizarlas comprobar si dicha llamada ya está resuelta. Si ya está resuelta cogeremos la solución del vector y si no la realizaremos. Obviamente cuando resolvemos una llamada la almacenaremos en el vector de soluciones.

Los pasos a seguir serían:
1. Crear un almacen (vector) con las posibles valores para los cuales resuelvo, n en el caso anterior.
2. Incializarlo a -1.
3. Modificar la función recursiva para que:
3.1 Almacene la solución de la llamada resuelta en el almacén.
3.2 Compruebe antes de realizar una llamada si dicha llamada ya está resuelta en el almacen.

Ahí queda eso… en los próximos dias pondre la solución definitiva. 🙂

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *