JS Algoritmos y Estructuras de datos VII: La recursividad III - Resolviendo problemas II

Bien en el post anterior vimos la primera de las opciones para compensar el problema del maximum call stack que nos podía dar la recursividad. En este post veremos algunas otras opciones para tener en nuestro arsenal, que cumplen (más o menos) con la resolución de nuestro problema aunque alguna sea bastante lenta y tengan el handicap de que debemos controlar la asincronía.

Usando setTimeout

En este caso vamos a jugar con el conocido setTimeout, en este punto es mejor que estemos familiarizados con el event-loop (recomiendo leer estos posts)

Usaremos este ejemplo, cambia un poco lo que teniamos antes, pero es por intentar seguir con el mismo concepto del sumatorio

let accum = 0
let number = 5

function addTo () {
	if (number === 0) { 
		console.log(accum)
		return
	}
	
	setTimeout(() => {
		accum = number + accum
		number--
		addTo()
	}, 0)
}


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

addTo()
finish()

Como vemos tenemos nuestra función addTo que si el número no es 0 pasa por un setTimeout con 0. Esto aunque no podamos verlo en la aplicación que lo incluye dentro de la task queue lo que hace es incluir el método en la timers queue y se ejecutaría según el ciclo de vida habitual de node cuando pase por los timers resueltos.

Veamos un poco lo que pasa cuando ejecutamos esto dentro de jv9000 (OJO que esto no funciona en la web tengo un fork modificado para permitir esto y otras cosas)

1. Incluye en el call stack la primera ejecución de addTo
   

2. Como number no es 0 se ejecuta el setTimeout, es decir, incluye la función anónima dentro de la timers queue, que para nosotros en nuestro visualizador esta dentro de la task queue
   

3. Importante, el paso anterior ha pasado como a un segundo plano dentro del event loop, por lo que para nosotros ha terminado la ejecución de addTo por lo que ya la podemos sacar del call stack
   

4. El loop continua y le toca a la función finish.
   
   Importante en este punto darse cuenta de que ha entrado la función finish al call stack se ha ejecutado y ha salido, sin que todavía hayamos tocado lo que tenemos dentro de task queue

5. Una vez ejecutada la función finish ya le toca el turno a comprobar task, al ver que tenemos algo lo pasa al call stack y lo ejecuta
   

6. Al ejecutarlo dentro del call stack, lo que tenemos de nuevo es otra ejecución de addTo, que repite la operación incluye en la task queue la función anónima del timeout
   

Y el proceso se repite n veces hasta que se cumple el number === 0

Donde terminaría nuestra ejecución. Como vemos aquí tenemos otro caso donde evitamos que la cola de llamadas se llene.

Usando setImmediate

Usando setImmediate es similar al setTimeout pero tiene menos pasos, en el caso anterior nuestra ejecución pasa por incluirse en la cola de task, comprobar el tiempo, ver que ha terminado incluirlo en el call stack y ejecutarlo. Al final son bastantes pasos. Sin embargo el setImmediate tiene su propia cola y se ejecutan al momento tras los eventos de I/O por lo que puede ser más rápido en un entorno recursivo. Veamos rápidamente la diferencia:

let accum = 0
let number = 5

function addTo () {
	if (number === 0) { 
		console.log(accum)
		return
	}
	
	setImmediate(() => {
		accum = number + accum
		number--
		addTo()
	})
}


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

addTo()
finish()

1. Al igual que antes se ejecuta la primera vez addTo
   
2. Al igual que antes pasa al finish, pero fijemonos que no tenemos en la cola de task, es decir, no estamos pendientes de que realmente termine nada.
   
3. De repente, si continuaramos ejecutando vemos como ha desaparecido todo y de repente aparece un método anónimo en nuestro call stack, que no es otro que la ejecución de lo que tenemos dentro del setImmediate
   
4. Y al igual que antes, este ejecutaría de nuevo nuestra función addTo
   

Este proceso se repetiría, veriamos como entra anonymous, luego addTo, termina addTo y desaparece, termina anonymous y desaparece, y en el siguiente ciclo todo se repite, hasta que coincide con number===0 que hace que se termine

Como vemos es bastante similar al proceso con setTimeout pero con menos pasos, esto no quiere decir que tenga que ser siempre más rápido, a fin de cuentas, ambos pasan por el event loop casi de la misma forma.

Usando process.nextTick

Por último veremos como será nuestra solución usando process.nextTick(). En este caso todo es igual que con setImmediate:

let accum = 0
let number = 5

function addTo () {
	if (number === 0) { 
		console.log(accum)
		return
	}
	
	process.nextTick(() => {
		accum = number + accum
		number--
		addTo()
	})
}


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

addTo()
finish()

En este ejemplo me ahorraré las imágenes ya que visualmente sigue el mismo proceso que setImmediate:

1. Se ejecuta la primera vez addTo
2. A continuación finish
3. Anonymous (lo que está dentro de nextTick)
4. addTo....
5. y el proceso se repite

Usando process.nextTick, tenemos otra solución pero en este caso, el beneficio es la velocidad, si echamos un vistazo a como se procesan las colas:

Podremos ver como nextTick se ejecuta tras cada hito dentro del loop, lo que significa que no tenemos que repetir el ciclo de vida del loop para volver a encontrarnos con el nextTick, como ocurre con los timers o el setImmediate.

Con esto de la recursión realmente lo que quería era mostrar un poco como solucionar problemas de maximum call stack y que se viera un poco que ocurre por dentro del event loop que no está de más tenerlo a veces en cuenta cuando tenemos ciertos problemas.

En siguientes posts de esta serie empezaremos con los algoritmos de búsqueda. Otro tema bastante interesante creo yo. Sin más, nos vemos en el siguiente un abrazoooooo