3 formas de obtener el Fibonacci de un número en JavaScript
Tags: spanish, javascript, beginners, dynamicprogramming
Published: 2022-04-08 22:32:49

---
title: 3 formas de obtener el Fibonacci de un número en JavaScript
published: true
date: 2022-04-08 06:00:00 UTC
tags: #spanish #javascript #beginners #dynamicprogramming
canonical_url: https://jfbarrios.com/3-formas-de-obtener-el-fibonacci-de-un-numero-en-javascript
---

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:

![Fibonacci Diagrams.drawio.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1649454539633/lgBfCuCOJ.png)

**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:

![Fibonacci Diagrams.drawio memorización.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1649454791812/eEso2vf6q.png)

**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?