JS Algoritmos y Estructuras de datos VI: La recursividad II - Resolviendo problemas I

Ya vimos en el post anterior cual es el problema principal que podemos tener en JavaScript a la hora de usar la recursividad. En un primer momento lo más probable es que nunca nos encontremos con este problema a no ser que trabajemos con una gran cantidad de datos, pero aún así, creo que ver como se soluciona este problema puede hacernos entender algunas cosas del funcionamiento de Javascript y como podemos usarlas para cualquier otro problema que nos encontremos.

Para resolver el problema de "Maximum call stack..." existen varias formas, veremos la mayoría aunque alguna puede que no me guste mucho.

Vamos con la primera Trampoline

Trampoline

Esta se fue extendiendo como una buena posibilidad para resolver el problema, pero personalmente a mí no me convence demasiado, creo que nos salimos un poco de la pureza del concepto de la recursividad pensando en su planteamiento más funcional. Veamos el código en cuestión:

const trampoline = (fn) => (...args) => {
  let result = fn(...args)
  while (typeof result === 'function') {
    result = result()
  }
  return result
}

function addTo(number, accum = 0) {
	if (number === 0) {
		return accum
	}
	return () => addTo(number - 1, number + accum)
}

function finish () {
  console.log('Finished')
}

console.log(trampoline(addTo)(5))
finish()

Más de uno se hará una idea de lo que realmente estamos haciendo en este caso y como cambia con respecto al ejemplo del post anterior sobre recursividad.
En este ejemplo tenemos una función addTo que no se llama a si misma, si no que, según el caso llama a una función anónima que la vuelve a llamar. Pero claro no podemos llamar solo a la función addTo ya que en la primera ejecución simplemente devolvería una función que no se ejecuta y terminaría nuestro programa. Lo que hacemos es crear una función trampoline que encapsularía cualquier otra donde queramos usar la recursividad. Esta función lo que hace es controlar si la respuesta es una función que debemos que espera ejecutarse o no, en resumen, trampoline es una función que se encarga o de devolver un resultado si se ha cumplido nuestro caso base o de ejecutar de nuevo la función, veamos ahora lo que pasa en nuestro call stack.

1. Se ejecuta trampoline
   

En cuanto a ejecutar, me refiero a, entre en el call stack y se ejecuta directamente.
Esto es una función con currificación, si nos fijamos lo que le pasamos como parámetro a trampoline es la función que queremos ejecutar, es decir, addTo.

2. Se ejecuta trampoline(addTo)(5)
   

Entra trampoline(addTo)(5) al call stack y comienza a ejecutarse, aquí como tenemos un bucle while donde se ejecutan otros métodos, veremos como el call stack crece

3. Se ejecuta por primera vez addTo con el valor 5
   

Como vemos estamos dentro de trampoline(addTo)(5) ejecutando addTo(5, 0)
Como el valor no es cero retorna la función anónima que ejecutaria de nuevo addTo

4. Se ejecuta la función anónima que a su vez ejecuta addTo(4, 5)
   

Esto devuelve de nuevo una función anónima, pero como tal su ejecución termina por lo que addTo sale del call stack

Y lo mismo sucede con la función anónima que su ejecución ha terminado y sale del call stack

5. Como el resultado de todo esto sigue siendo una función nuestro trampoline vuelve a ejecutar la función anónima que ha recibido
   

Donde a su vez se ejecuta addTo(3, 9)

6. Este proceso se repite hasta que el parámetro number === 0 donde termina la ejecución de la función anónima dentro de trampoline
   

7. Se ejecuta el resultado de console.log(trampoline(addTo)(5)) que nos muestra 15
   

8. Se ejecuta finish()
   

Entra dentro del call stack

9. Ejecuta el console.log dentro de la función finish
   

Y la ejecución de nuestro programa o script termina

Como vemos esto es un truquillo que hace que no saturemos el call stack de ejecuciones pendientes, que cubre la necesidad que tenemos aunque como digo no es algo que me convenza mucho.

Esta es una de las formas que tenemos para evitar el Maximum call stack, en los siguientes post veremos otras posibles soluciones, algunas más sencillas otras más complejas, pero nos serviran para entender del todo como funciona el call stack.

Nos vemos en el siguiente un abrazoooooo