Fibonacci, ¿vale? Fibonacci este es el típico ejemplo en el que, bueno, no sé si sabéis exactamente qué o quién es Fibonacci, pero básicamente es una secuencia de números, esta de aquí, esta es la típica secuencia, bueno, yo lo llamo sucesión, serie de Fibonacci,
que es infinita en el que tú básicamente es 0, 1 y luego es este más el anterior es el siguiente, este más el anterior es el siguiente, 2 más 1, 3, 3 más 2, 5, 5 más 3, bla, bla, bla, y así hasta el infinito.
Esto es muy típico en la universidad y todo este tipo de cosas, pero bueno, también las pruebas técnicas lo suelen hacer mucho porque hay veces que puedes hacerlo con recursividad
y puede ser bastante challenge el tema de hacerlo con recursividad, aunque ya verás que está tirado hacerlo con recursividad, y también se puede hacer sin recursividad,
que además es bastante más óptimo. De hecho, creo que, si no recuerdo mal, con recursividad, o sea, claro, recursividad, recursividad,
tendría que explicar el bcow, pero creo que es 2n, y en cambio sin recursividad es una iteración, o sea, es n.
Esto ya lo explicaré otro día porque si me puedo hoy hablaros del bcow, entonces ya sé que nos quedamos solos.
Entonces, ¿utilizamos recursividad en mi trabajo? Alguna vez hemos utilizado recursividad, pero muy poco.
Midu, ¿ignoraste mi suscripción? Lo siento, es que me he perdido. ¿Para cuándo nos enseñas a hacer un componente open source?
Ah, pues algún día de esto, tampoco, no es muy difícil. Por primera vez en 4 años trabajando con JavaScript vendiendo el disk.
¡Qué grande! Me encanta. Vale. Bueno, pues entonces tenemos, vamos a hacer Fibonacci, lo más típico, lo más fácil,
cuando te dicen de hacer, voy a llamarle Fibonacci, es hacerlo con recursividad.
Lo más importante de la recursividad es tener un if. Este es el primer paso de cualquier cosa recursiva que quieras hacer,
porque siempre tienes que tener una salida, una salida de la recursividad, porque si no tú estás todo el rato
ejecutando el mismo método y al no tener ninguna salida, ningún escape, lo que va a ocurrir es que tengas como una pila infinita de ejecuciones
que al final nunca se ejecutarán y seguramente reventará tu ordenador y se quedarás en todo el bloque sin electricidad y este tipo de cosas.
En el caso de Fibonacci hay diferentes estrategias de salida. Por ejemplo, yo, para empezar, luego hay una forma más fácil,
pero cuando se quieren tratar de... Mira, voy a copiar la secuencia para que lo veamos, ¿vale?
Porque esta estrategia, y por eso está muy bien Fibonacci, esta estrategia está muy bien para cualquier algoritmo en el que te tengas que enfrentar,
que es el hecho de tener los casos más simples y a partir de ahí ir iterando.
Por ejemplo, Fibonacci hemos visto que es así, ¿vale? 1, 2, 3, esto 5 y bla, bla, bla.
Vale. Joder, con el dirnein, la madre que lo parió. Vale, entonces ya sabemos que n cuando es 0, el resultado es 0.
n cuando es 1, el resultado es 1. n cuando es 2, el resultado es 1 más 0, ¿vale?
Pero ya vemos que los dos casos más simples, que es n0 y n1, lo que podrías empezar a escribir sería, vale, pues cuando n es 0, entonces devuelvo 0.
Cuando n es 1, entonces devuelvo 1. Hasta aquí podrías hacerlo bien. Luego ya veremos que hay otra forma de hacerlo mucho más simple, ¿no?
Porque lo que puedes hacer simplemente es decir, bueno, pues si n es menor que 2, entonces devuelvo n.
Porque ya te habrás dado cuenta que si n es 0, devuelve 0. Si n es 1 y devuelves 1, pues cuando n es menor que 2, solo devolviendo n, ya lo tendrías, ¿vale?
Entonces ya lo tendríamos aquí. Esto con los casos más simples. Por lo tanto, si yo ya hago Fibonacci 0, pues esto me debería dar 0.
Si hago Fibonacci 1, me debería dar 1. Pero si hago Fibonacci 2 y Fibonacci 3, pues vamos a ver que esto me debería dar 1 y esto me debería dar 2 y tal.
Bueno, entonces ya vemos que me está dando undefined y por eso no veo nada aquí. Así que vamos a solucionar esto.
Para hacerlo, lo que puedes hacer, ya que lo tenemos así, es simplemente hacer aquí devolver lo que tenemos que calcular.
Y lo vamos a hacer con recursividad. ¿Cómo funciona Fibonacci?
Lo que estamos viendo es que estos dos casos ya los tenemos arreglados, pero este tercer caso, ¿cómo se calcula?
Con 1, que es el anterior, más el anterior. ¿Y cómo sabemos cuáles son los valores que tenemos aquí de los anteriores?
Bueno, pues lo que podemos hacer es Fibonacci. Vale, vamos a sumar Fibonacci n-2. ¿Por qué?
Porque si le pasamos 2, lo que queremos justamente, cuando sea 2, n-2 va a ser este 0.
Y tenemos que sumarle Fibonacci n-1. Y con esto, con esto ya estaríamos sumando básicamente.
Esta es la recursión. ¿Por qué es la recursión? Porque fíjate, cuando ya estamos en n3, lo que va a ocurrir...
Claro, aquí la primera vez que se ejecutan, bastante sencillo, ¿no? Porque esto, n-2, esto es 0.
Y n-1, pues esto sería 1. Y por lo tanto, a ver, es recursivo, pero lo controlamos bastante bien
porque ya sabemos que esto va a devolver 0 y esto va a devolver 1. Entonces es fácil.
Pero cuando vamos iterando más, si vamos al 3, vamos a ver que 0, 1, 2, 3.
El 2, por ejemplo, ya sabemos que es 1 más 1. Vale, este es fácil. Pero el 3 es 2 más 1.
¿Pero cómo sabes que esto era 1? Lo sabes en realidad por el anterior. Y así igual, 5 más 3, o sea, esto que sería 8.
Vamos con el 8. 5 más 3. ¿Pero cómo sabes que esto era un 3? Pues esto lo tienes que saber porque esto era un 2 más 1.
¿Y cómo sabías que esto era un...? ¿Sabes? Ya vas viendo un poco por dónde va el tema de la recursión.
Así es que está ocurriendo la recursión. Lo que va a pasar es que al final, cuando esto de forma recursiva se vaya llamando,
va a ir calculando lo que son los valores anteriores. Y de esta forma va a ir creando los valores anteriores.
Pero va a llegar a un punto donde va a entrar aquí y, por lo tanto, llegará y parará aquí, en el 0 y en el 1.
Porque ya sabrá esos valores. Llegará hacia atrás, irá hacia atrás, pero al llegar aquí dirá, vale, ya no me voy a seguir llamando.
Se acabó la recursividad. Tiene como una parada justamente aquí. Eso sería la recursividad y tener en cuenta cómo podemos calcular Fibonacci.
Muchas veces cuando la gente hace esto, esto está bien. Y la verdad es que está bastante bien porque la gente se entiende muy bien,
se ve claramente cómo funciona el algoritmo. El problema es que normalmente, claro, esto no es muy óptimo porque, como comentaba antes,
esto es exponencial, es 2 elevado a la n. Y, claro, al final, ¿por qué? Porque encima estás haciendo recursividad por cada uno de los casos,
casos que además ya has calculado. O sea, es un poco rollo. Esto se puede simplificar bastante.
Pero, bueno, para entender la recursividad está bastante bien. Ahora, ¿cómo se puede hacer? Y esto muchas veces lo dicen, ¿no?
Dicen, vale, ahora has hecho recursividad, o sea, has hecho Fibonacci con recursividad y entonces te dicen, vale,
pero esto tiene un problema de que la complejidad algorítmica es tal. ¿Cómo podrías hacer una más fácil?
La forma más fácil de hacer Fibonacci, aparte de hacerlo así, mira, de hecho, vamos a poner aquí todos los, algunos casos,
para que veamos que esto está funcionando, vale, 5, esto es 5, vamos a poner Fibonacci 10, vamos a quitar esto, que son muy típicos,
y vamos a poner aquí este 55, Fibonacci 100, hostia, 100 igual me he pasado, ¿eh? Me he pasado porque Fibonacci escala,
escala muy chungo. No, me lo he cargado, me lo he cargado. Sí, me lo he cargado. Que tened en cuenta que es muy,
muy, muy chungo la recursividad cuando esto, claro, es lo que os digo, que esto parece que no. Mira, ahora, 610.
Esto escala rapidísimo. Mira, ya 18, 20, ¿se ponemos 40? Uf. Bueno, pero escala bastante, bastante mal.
Venga, vamos a poner esto y vamos a ponerle un console time, a ver si puedo ver aquí cuánto, más o menos.
Fibonacci, a ver cuánto tarda. Con el console time debería decirnos más o menos cuánto ha tardado.
A ver si esto es capaz. 610, no, no es capaz, porque nos dice 0.000, ah, un milisegundo.
A ver si ponemos 18, 20, 25, 50. Con 50 sí que he tardado bastante.
Tardaba segundos. O sea, vamos a ponerle menos, que 50 parece bastante.
Hostia, no me jodas que otra vez me lo he cargado otra vez.
40, era 40. Sí, sí, ya. Vale, vale.
Era 40, perdón. No se ve el tiempo. Bueno, no es importante.
A ver. Vale, ya está. Hostia. Vale.
Mira. Bueno, no se ve el tiempo, pero son...
1,7 segundos, más o menos. Vale.
Para que os lo digo yo, más o menos.
Vale.
Vale, es que no sé.
Es que para enseñarlo es un poco complicado.
Pero mira, ahí sale, ¿vale?
1.165 milisegundos, ¿vale?
Vale. Entonces, ¿cómo podemos hacer esto con recursividad?
Y está bastante bien.
Y si lo hacéis con recursividad puede estar bien.
Pero es posible que os hagan el challenge de...
Vale, lo podéis hacer sin recursividad.
Porque, claro, con recursividad es bastante lento.
Y no es calabin para grandes valores.
Entonces, hay diferentes formas de hacerlo.
Y aquí dependerá también cómo lo que queráis...
La idea que tengáis, por ejemplo, una cosa que podéis hacer
es tener aquí FIP, donde vais a tener las...
Bueno, los valores, básicamente.
Que sería la posición 0, pues va a ser la 0.
La N1, la 1.
Y aquí podríamos tener los datos.
Que son los que...
Donde vamos a estar guardando.
Bueno, los datos no los vamos a necesitar.
Vamos a guardarlo todo en FIP y ya está, ¿vale?
Tienes diferentes estrategias de loop.
Puedes utilizar lo que te dé la gana.
Pero para que se vea bastante claro,
yo lo voy a hacer con un for, ¿vale?
Lo podemos hacer que empiece a partir del 2.
Porque ya tenemos el 0 y el 1.
Así que decimos que empieza a partir del 2.
Y mientras la I sea más pequeña que la N,
que es lo que nos han pasado,
lo que vamos a hacer es seguir incrementando el iterador, ¿vale?
Y aquí, ¿qué es lo que tenemos que hacer?
Pues lo que tenemos que hacer es ir calculando los valores
que tiene Fibonacci, o sea, la serie.
Así que en cada una, por ejemplo, en FIP y en la posición I,
que en este caso, pues digamos que es la 2, ¿vale?
Pues tenemos que hacer, ¿qué?
Pues el cálculo que hemos hecho aquí.
Fibonacci.
Ahí.
No, sí, Fibonacci.
No, no tenemos que llamar a Fibonacci.
Sino que utilizamos lo que ya tenemos en el array.
¿Y qué es lo que tenemos en el array?
Pues seguro que tenemos ya calculadas las series anteriores.
Así que las utilizamos aquí.
En este caso, bueno, aquí antes he puesto esto,
pues lo hacemos así igual, para que lo veamos igual.
¿Y qué es lo que tenemos que devolver?
Pues simplemente deberías devolver Fipn.
Total, el loop tampoco se va a ningún sitio.
Y ya está.
Lo que tendríamos aquí es un array,
donde es donde vamos a estar guardando
lo que sería la serie de números de Fibonacci.
La N0 es 0, N1 es 1.
Ahora, hacemos un bucle donde empezamos con el 2,
que la N es 2, pues no pasa nada,
porque al final entrará una vez.
Que la N es 1, pues no pasa nada.
No entrará ninguna vez.
Y no entrará en el for.
Simplemente N es 1, el for no lo necesita.
Fib 1, pues ya tenemos aquí que es 1.
Ya tenemos aquí los valores base.
Y ya está.
Es que no tiene mucho misterio.
Lo importante es esto.
¿Por qué?
Porque aquí lo que vas haciendo
es ir guardando la serie de números,
que era el problema que estábamos teniendo aquí
y que por eso tenía esa complejidad.
Porque constantemente lo que iba haciendo,
por eso tiene una complejidad de 2 elevado a la N.
Porque básicamente, si te fijas,
lo que estamos teniendo aquí
es una bifurcación, ¿no?
Donde se va a la izquierda y derecha
y está calculando constantemente los mismos números.
Que eso se podría mejorar
con algún tipo de caché, con cosas así.
Pero aún así, no vale la pena tener una caché
cuando justamente con un loop hacia adelante
lo tienes justamente ya arregladísimo
y no necesitas tener ningún tipo de problema.
Y con esto ya lo tendrías.
Vas calculando esto y ya está.
Ahora, como podéis ver,
bueno, no sé si lo podéis ver,
pero os lo enseño ahora.
Ahora tarda 0 milisegundos.
O sea, ya podéis notar que justamente,
justamente, no sé, pongo 50.
Ahora, fíjate la diferencia, ¿no?
Antes, con recursividad,
estábamos teniendo que estaba tardando tiempo, ¿no?
Y se quedaba incluso penchado.
Y ahora, vamos a intentar el de 100.
Fíjate, ¿eh?
El de 100.
Para que os deis cuenta de que hay veces
que sí que vale la pena
el hecho de optimizar los algoritmos.
No es que sea un caso de uso
de que en el desarrollo web
vais a tener este problema,
pero con un simple array
donde justamente, hombre, 0 milisegundos.
No está nada mal.
En cambio, en el otro,
con la recursividad,
podíamos ver que se quedaba congelada
y toda la pantalla con el cálculo
para que lo tengáis en cuenta.
Y esta sería la forma mucho más sencilla, ¿vale?
La forma más sencilla de Fibonacci
que no sé por qué,
no sé por qué la gente no...
No sé.
Creo que como se utiliza Fibonacci
para el tema de la recursividad,
ya le he puesto mil, forkeon.
Ah, no, mil no.
Mil igual es demasiado, ¿eh?
Pero no creo que pase nada
porque, mira, he puesto 500
y sin problema, ¿eh?
Mira, mil.
Aquí tienes mil
y ahí tengo el resultado
y ha tardado un mil segundo.
Es bastante más rápido.
Es bastante más rápido.
Sin recursividad, además,
se entiende bastante mejor.
Pero bueno,
sí que me parece un ejemplo
muy interesante
para aprender recursividad
porque se entiende bastante bien,
pero creo que, obviamente,
con Fibonacci así,
sin recursividad es bastante...
¿Qué es lo que no has entendido?
¿Qué alguien ha dicho?
No he entendido.
Dudo que sea cero.
El range es que no lo muestra bien.
Puede ser, ¿eh?
O sea, no es que sea...
Claro, hay que entender
que también está haciendo un redondeo.
No es que sea cero milisegundos
como una ausencia de tiempo,
sino que simplemente,
a lo mejor,
es tan rápido
que no es capaz de expresarlo
en milisegundos.
Eso sería.
La recursividad es solo para explicar
por qué la recursividad es mala.
Normalmente,
la recursividad no es la mejor.
No es la mejor normalmente.
Pero, bueno,
hay veces que sí que te puedes solucionar
algunas cosas.
¿En qué casos es bueno usar recursividad?
Normalmente,
a ver,
en tema de árboles,
pero claro,
es que aquí se está generando
un árbol también.
En tema de árboles
puede ser que esté bien
a la hora de buscar,
pero es que casi siempre
hay una solución mejor.
Casi siempre hay una solución mejor.
Porque es que la recursividad
suele ser muy cara.
Y sobre todo en JavaScript.
Ese es el problema.
Claro,
recursividad es útil
cuando creas el menú y el submenú.
Claro,
pero porque ahí la recursividad,
por ejemplo,
la recursividad también a veces
es interesante
cuando creas menú y submenú
con React,
con componentes de React.
Pero claro,
es que la recursividad ahí
es muy poco costosa
porque son muy pocos números.
Pero el problema
de la recursividad
es que no escala.
Escala muy poco.
Muy, muy, muy poquito.
Muy poquito.
Así que normalmente
está bien
para hacer algunas cosas,
claro,
para aplanar un objeto.
Pero ves,
para aplanar un objeto,
porque al final
lo que tienes que hacer
es como ir profundizando,
pero el problema llega
que hay veces
que es demasiado...
Si el objeto
fuese muy grande
al final
estaría fatal.
Estaría ya fatal.
La recursividad sería buena
si ya ha escrito
optimizara.
Qué bueno.
Vale, a ver,
que vamos con otro.
¿Por qué...?
¿Por qué...?