Hablemos ahora de la Recursividad. A la gran mayoría por lo menos nos tiene que sonar ¿no?... por lo menos nos habrán dicho que es muy chula, que mola usarla, que porque no lo pruebas... pues bien he de coincidir con casi cualquier cosa buena que se diga sobre este concepto, aunque claro lo suyo es usarlo cuando toque y tenga sentido (pero eso es otra historia).
Por ahora veremos que es esto de la recursividad, para que nos sirve y cual es el problema que nos generará a la larga (y como resolverlo) esto en nuestro querido Javascript.
Recursividad
No me voy a extender en explicaciones técnicas en este caso (profundizaré más en el post de la línea de javascript funcional), por lo que, en palabras simples, es la capacidad de una función de llamarse a si misma. Esto es más un concepto de programación funcional, pero debido a que las funciones en javascript se pueden tratar como cualquier otro objeto (ciudadano de primera clase), es decir, que se puede pasar por parámetro, retornar dentro de otra función.... y todo lo que se nos ocurra, podemos hacer uso de la recursión también.
Algunos ejemplos de su uso podrian ser: Recorrer un sistema de ficheros (abrir primera carpeta, recorrer lo que hay dentro y si encuentra una carpeta la abre y recorre...y asi sucesivamente), se suele ver en la típica resolución de problemas sobre los números de Fibonacci (que es y ejemplos aquí) o en general cualquier problema que requiera repetir lógica sobre un mismo elemento (y no necesitemos o no tenga sentido funcional que usemos un bucle de los habituales)
Veamos cuales son los detalles de una función recursiva. Ya hemos comentado que en la teoría se supone que es una función que se llama a si misma, como por ejemplo
function addTo (number) {
return number + addTo(number - 1)
}
addTo(10)
La teoría de la función sería que queremos sumar los números desde 0 hasta el número dado. Visualmente tiene sentido, ¿no?, sumamos el número que recibimos primero que sería el 10 y luego llamamos a la misma función para que use el 9 y así sucesivamente. Pero claro si nos fijamos bien aquí tenemos un problema, si ejecutaramos esto tendriamos un bucle infinito porque en ningún momento le indicamos cuando tiene que parar. Lo que le falta a esta función es lo que se conoce como caso base.
El caso base es la unidad mínima que debe devolver una función recursiva, si pensamos en lo que queríamos hacer que era sumar del 0 al 10, en este caso nos falta indicarle que cuando llegue a 0 nos devuelva el número, este sería nuestro caso base, siempre debe tener un caso base.
function addTo(number) {
if (number === 0) {
return number
}
return number + addTo(number - 1)
}
addTo(10)
Si ahora ejecutamos esto todo iria bien y nos debería devolver 55. Esto es un caso muy sencillo para explicar que es la recursión pero veamos rápidamente que es lo que lo pasa por debajo.
Para ello lo primero es repasar que es el call stack. El call stack o pila de llamadas (lo defino a mi rollo por simplicicad) son las funciones que se tienen que ejecutar (con estructura LIFO) dentro de un Task del event loop. En el próximo post profundizaremos más en que es cada cosa y el flujo que sigue el eventloop, con lo que nos tenemos que quedar ahora mismo es que el call stack es el trabajo que tiene pendiente javascript para poder pasar a la siguiente tarea (es decir que nuestro thread esta bloqueado hasta que termine).
Para verlo bien vamos a usar una herramienta que me he encontrado (grandisima ayuda para entender esto visualmente ya lo veremos, agradecer a los creadores) que es jsv9000. Esta herramienta nos permite comprobar visualmente lo que pasa dentro de nuestro eventloop en cada una de sus Queues.
Lo que haremos será añadir el código siguiente y darle a run:
function addTo(number) {
if (number === 0) {
return number
}
return number + addTo(number - 1)
}
function finish () {
console.log('Finished')
}
addTo(5)
finish()
Lo que hace la herramienta es indicarnos en que puesto está nuestro código y que ha ido pasando por dentro paso a paso, por lo que tenemos que ir dandole a step. Si le damos 6 veces (como le hemos indicado que hasta 5 y empezamos en el 0) vemos como el código lo único que ha hecho es incluir 6 llamadas en el call stack de la función de suma en la fase de evaluación
Si le continuamos dando a step vemos como se va vaciando el call stack de la función y lo siguiente es el método finish que nos muestra el resultado del console.log. En este caso lo que vemos es que nuestra función recursiva va acumulando llamadas en el call stack hasta que llega al caso base y empieza a devolver datos y a vaciar. Si lo queremos ver más claro añadimos unos logs
function addTo(number) {
if (number === 0) {
console.log(0)
return number
}
const result = number + addTo(number - 1)
console.log('result: ', result)
return result
}
function finish () {
console.log('Finished')
}
addTo(5)
finish()
Y podemos ver en acción realmente donde estamos
Una vez entendido esto, ahora os planteo el gran problema que resolveremos en próximos posts. Cambiemos el código por lo siguiente pero no recomiendo ejecutarlo en la herramienta que tardaría muchisimo, ejecutarlo en la consola del navegador, en un fichero de node o donde más os guste
function addTo(number) {
if (number === 0) {
return number
}
return number + addTo(number - 1)
}
console.log(addTo(100000))
Fijaos el número que he puesto 100000, esto nos debe dar un error como el siguiente:
Es decir hemos llegado al límite de acciones posibles dentro de la pila de llamadas, si nos planteamos lo que ocurria con 5, que teniamos 6 inclusiones el call stack, ahora tendríamos 100001 (se que este número es muy grande pero depende de lo que estemos haciendo o donde puede ser mucho menos, realmente insisto en que es un error muy habitual). Este problema viene dado porque javascript no es un lenguaje orientado a este tipo de funciones, pero siempre podemos encontrarle solución, en los próximos post veremos como podemos solucionar esto de muchas maneras, mientras tando plantear vosotros posibles soluciones. Nos vemos en el siguiente un abrazoooooor