Un número Fibonacci, usualmente con notación f(n), es la suma de los dos números fibonacci que le preceden. Esta sucesión empieza con f(0) = 0, f(1) = 1, f(2) = f(1) + f(0) hasta f(x) = f(x-1) + f(x-2).

En este artículo veremos tres formas diferentes de encontrar un el resultado de aplicar la sucesión a un determinado número.

Recursión

Si usamos un sistema de recursión para calcular resultado de fibonacci para determinado número, por ejemplo 5, lo que obtendríamos es algo parecido a esto:

Algoritmo

1. Debemos revisar que el número n que le estamos pasando a la función es igual o menor que 1, si este es el caso tenemos que devolver n como el resultado de la función.
2. En caso contrario, la función se volverá a llamar a sí misma, pasándose como argumento el cálculo de n-1 y n-2 respectivamente, posteriormente devolverá como su resultado la suma de ambas invocaciones. ​ Implementación

Complejidad (Time Complexity) No entraré en detalle sobre cómo calcular la complejidad computacional, pero les dejo acá que es: 2^n, por lo que podemos ver que entre más grande sea el número, crece enormemente la cantidad de recurso computacional que necesitamos es enorme.

Programación Dinámica Top-Down con memorización

El primer enfoque de programación dinámica que quiero que veamos es de top-down. La idea aquí es similar al enfoque recursivo, pero la diferencia es que guardaremos las soluciones a los subproblemas que encontremos.

De esta forma, si nos encontramos con el mismo subproblema más de una vez, podemos usar nuestra solución guardada en lugar de tener que volver a calcularla. Esto nos permite calcular cada subproblema exactamente una vez.

Esta técnica de programación dinámica se llama memorización. Podemos ver cómo nuestro árbol de subproblemas se reduce cuando usamos la memorización:

Algoritmo

1. Debemos revisar que el número n que le estamos pasando a la función es igual o menor que 1, si este es el caso tenemos que devolver n como el resultado de la función.
2. En caso contrario, revisaremos si el subproblema ya ha sido solucionado con anterioridad, de no ser así, entonces procederemos a realizar el mismo proceso que utilizamos en la recursividad y guardaremos el resultado
3. Devolveremos el resultado que hemos guardado, ya sea porque se haya computado por primera vez o por que ya lo hayamos calculado previamente.

Implementación

var fib = function(n) {
    const map = new Map(); // creamos un mapa para guardar los valores

    const dp = (x) => {
        if (x <= 1) return x;

        if (!map.has(x)) { // si NO hemos calculado el resultado
            map.set(x, dp(x-1) + dp(x-2)) // lo calculamos y guardamos el valor
        }

        return map.get(x);
    }

    return dp(n);
};

Complejidad Para este escenario la complejidad será de O(n), una complejidad mucho menor comparada con la de recursividad.

Programación Dinámica Bottom-Up

En el enfoque de programación dinámica Bottom-Up, lo que buscamos es solucionar los subproblemas en un orden diferente, es decir, primero resolvemos f(2), luego f(3), luego f(4) y así hasta llegar a f(n). De esta forma no tenemos que memorizar nada, puesto que únicamente calcularemos aquellos subproblemas que son necesarios.

Algoritmo

1. Tendremos un array donde iremos almacenando los valores de cada subproblema, este lo inicializaremos con los resultados base 0, 1.
2. Recorreremos desde la posición 2 hasta llegar a n (incluyéndola) para añadir la solución de cada subproblema.
3. Devolveremos luego nuestro array en la última posición.

Implementación

var fib = function(n) {
    const sol = [0, 1];

    for (let i = 2; i<= n; i++) {
        sol[i] = sol[i -1] + sol[i - 2];
    }

    return sol[n];
};

Complejidad En este caso la complejidad computacional sigue siendo de O(n).

Bonus

El cálculo de complejidad no solo se debe considerar a nivel computacional, también a nivel de uso de memoria, por lo que si vemos, por ejemplo, la solución Bottom-Up, no es óptima puesto que hemos guardado en memoria datos predecesores que no son necesarios.

Es más fácil visualizarlo si pensamos en que queremos el fibonacci de 10, tendríamos algo como [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55], pero realmente para tener el fibonacci de 10 solo es necesario tener en memoria los últimos 2 valores 21 y 34.

Implementación

var fib = function(n) {

    if (n <= 1) return n;

    let prev2 = 0;
    let prev1 = 1;
    let c = 0;

    for (let i = 2; i<= n; i++) {
        c = prev1 + prev2;
        prev2 = prev1;
        prev1 = c;
    }

    return c;
};

Conclusiones

Hemos llegado hasta el final del artículo, déjame saber qué te ha parecido las soluciones, ¿cambiarías algo?, ¿hay algo que no entiendes?