ES6 - De la recursividad a la recursividad de cola

La próxima versión de JavaScript (ECMAScript 6) introducirá una característica de programación increíblemente potente llamada Tail Recursion, una característica que me entusiasma. En este artículo quiero hablar un poco sobre la recursividad frente a la iteración, la recursividad de cola y lo que significa para el futuro de JavaScript.

Recursión

Siempre ha sido una característica poderosa dentro de JavaScript, y muchos otros lenguajes de programación, como un medio para resolver problemas mediante la descomposición de las cosas en versiones más simples / más pequeñas de sí mismos. Uno puede pensar en ella en el contexto de la programación, como una función que se llama a sí misma, pero con argumentos cambiados o reducidos. La estrategia recursiva de resolución de problemas a menudo produce resultados bastante elegantes, con un código más legible y claro en comparación con otros enfoques, como la fuerza bruta o la iteración. Sin embargo, si la tarea en cuestión es profundizar en grandes cantidades de datos anidados, tenemos que tomar una decisión: ¿recurrencia o iteración? Empecemos con algo de código…

A continuación se muestra una función factorial, el ejemplo de recursión por excelencia utilizado en muchos lenguajes de programación - nada demasiado loco o emocionante.

función factorial(n) { return n === 1 ? 1 : n * factorial(n - 1); }

Para hablar de la función, factorial() simplemente toma un argumento numérico, digamos 6, y multiplica el argumento por el factorial del argumento restado por 1, que a su vez vuelve a tomar ese argumento y lo multiplica por el factorial de 1, etc., hasta que el argumento es 1 y la función devuelve - ay tienes recursividad.

El retorno de 1 denota la condición de terminación (o caso base) requerida por una función recursiva, mientras que el resto de la función continúa ejecutándose y llamándose recursivamente a sí misma hasta que se cumple el caso base. Mientras que esta simple función factorial puede parecer fina y elegante desde una perspectiva de limpieza, hay algunas implicaciones muy grandes que ocurren detrás de las escenas de cómo ejecutamos nuestra llamada factorial. Una gran manera de entender cómo factorial() va a ir sobre su ejecución sería visualizar la pila que se crea.

A continuación verás una representación aproximada de lo que más o menos ocurre entre bastidores cuando ejecutas una función recursiva en las implementaciones actuales de JavaScript.

factorial(6) // asignar memoria y guardar estado 6 * factorial(5) // asignar memoria y guardar estado 6 * (5 * factorial(4)) // asignar mem... 6 * (5 * (4 * factorial(3))) // asignar mem... 6 * (5 * (4 * (3 * factorial(2)))) // asignar mem... 6 * (5 * (4 * (3 * (2 * factorial(1))))) // asignar mem... 6 * (5 * (4 * (3 * (2 * (1 * factorial(0)))))) // allocate mem... (max depth) 6 * (5 * (4 * (3 * (2 * (1 * 1))))) 6 * (5 * (4 * (3 * (2 * 1)))) 6 * (5 * (4 * (3 * 2))) 6 * (5 * (4 * 6)) 6 * (5 * 24) 6 * 120 720

En primer lugar, tenemos que tener una idea de cómo esto computa con el fin de entender el espacio y la complejidad del consumo de memoria. Arriba, tenemos este árbol recursivo en cascada, donde cada llamada a función se apila en memoria para ser asignada para su uso en la siguiente llamada recursiva. Cada recursión ocupa espacio porque una vez que llamamos a factorial(6) estamos acumulando operaciones diferidas que eventualmente se realizarán después de que se complete la llamada recursiva final. Hay una subida y bajada del espacio asignado, por lo que para factorial(n) estamos asignando n lugares en la pila. Una representación gráfica de este consumo de memoria en relación con el tamaño de la llamada recursiva podría parecerse al siguiente gráfico.

A partir de este gráfico podemos declarar que el uso de memoria es ilimitado (no es algo bueno). Observa cómo el consumo de memoria crece con la adición de cada llamada recursiva. Eventualmente, este aumento sin límites de la memoria acabará con nuestra capacidad de ejecución, ya que reventamos la pila, o lo que se llama un desbordamiento de pila. La cantidad de capacidad recursiva varía dependiendo de las implementaciones del motor del navegador y sus respectivos tamaños de pila de llamadas. Una forma en la que podríamos echar un vistazo a los límites de tamaño de la pila de llamadas de las implementaciones de los distintos navegadores sería envolver una llamada recursiva en una captura try, capturando así nuestro límite y preservando nuestra ejecución, ver más abajo.

function count(num) { try { return count((num || 0) + 1); } catch(e) { return num; } }

Esta función continuará recurriendo hasta que el tamaño de la pila de llamadas exceda la cantidad de memoria, dándonos una estimación del tamaño de la pila de llamadas de los respectivos entornos. Pruébalo en varios navegadores para comparar cada uno de sus límites.

Iteración

La información anterior nos lleva a pensar que el uso de la recursividad en JavaScript podría considerarse poco práctico (dependiendo del tamaño de pila de llamadas necesario), después de todo, cualquier algoritmo que pueda implementarse utilizándola también puede implementarse utilizando la iteración. Veamos un ejemplo de cálculo del factorial de un número mediante iteración frente a recursión.

// via Iteración function factorial(n) { if (n === 0) { return 1; } else { var sum = 1; for (var i = 1; i <= n; i++) { sum = sum * i; } return sum; } }

Lo anterior, en mi opinión, es menos elegante y legible que la versión recursiva declarada anteriormente. Tampoco utiliza del todo el aspecto funcional de JavaScript que a menudo se considera una de las mejores partes del lenguaje. Sin embargo, un enfoque de bucle iterativo para el problema factorial nos impediría añadir elementos a la pila de llamadas y, por tanto, producir un consumo limitado de memoria.

De todos modos, vamos a fingir que los bucles son feos, y recordar cómo nos gusta el código elegante, limpio y legible, así que vamos a volver a ese estilo recursivo. No hay problema, ES6 viene al rescate con esta nueva característica llamada recursividad de cola - pero primero, ¿qué es exactamente la recursividad de cola?

Recursividad de cola Recursividad

¿Qué es la recursividad de cola? Básicamente, en lugar de hacer una invocación de la función recursiva como sentencia de retorno (llamando a una nueva versión de sí misma), hace un salto y reutiliza el mismo contexto (o registro de activación) de la llamada recursiva anterior, es decir, sin coste de memoria añadido. Lo que esto significa es que a medida que utilicemos una recursividad de cola adecuada en nuestras funciones recursivas, el uso de memoria se mantendrá estable en lugar de aumentar continuamente con cada llamada recursiva. Por ejemplo, una versión recursiva de cola correctamente implementada del uso de memoria de la función factorial podría parecerse a esto.

Comparemos esto con el gráfico anterior y de repente seremos programadores mucho más felices. En lugar de añadir llamadas a la pila y consumir memoria, las pilas y contextos anteriores serán liberados (o reutilizados) y recogidos de la basura, evitando un crecimiento continuo del uso de memoria. Así que todo es genial y la recursividad de cola viene a salvar el día (más o menos). Antes de entusiasmarnos demasiado, debemos tener en cuenta algunas advertencias. Para hacer una recursión de cola adecuada, necesitamos satisfacer tres cosas.

• estar en modo estricto

• escribir nuestros programas en la forma adecuada de llamada de cola

• estar en un entorno optimizado para llamadas de cola (TCO)

La primera de esas tareas es fácil, si quieres aprender más sobre el modo estricto echa un vistazo a los recursos MDN aquí. Recomiendo a todos los desarrolladores de JavaScript que lo utilicen.

La segunda tarea de la forma adecuada de llamada de cola es un poco más complicado. Desafortunadamente, nuestra función factorial recursiva elegante declarada anteriormente no calificaría para la recursividad de cola incluso en un entorno optimizado de llamada de cola. No está en la forma apropiada de llamada de cola, déjame explicarte…

Una llamada a la cola correcta es cuando lo último que hace una función es devolver el resultado de llamar a otra función. En la función anterior el ternario resaltado else devuelve el resultado de n * factorial(n - 1), en otras palabras no es una función independiente, y como resultado necesitaría retener la pila. Un ejemplo de una función factorial con llamadas de cola adecuadas (ver más abajo), observe que el ternario else devuelve recur(n - 1, n * acc) como una invocación independiente. Nótese que esta versión de una función factorial recursiva con llamadas a la cola es un poco más complicada, sin embargo calificaría para TCO y por lo tanto nos daría el poder de la recursión a la cola.

// via Tail Recursion function factorial(n) { function recur(n, acc) { return n == 0 ? acc : recur(n-1, n*acc); } return recur(n, 1); }

Para mayor claridad, aquí se puede ver un ejemplo demasiado simplificado de una función no recursiva en la forma adecuada de llamada de cola. La función de abajo tiene la posibilidad de optimización de llamada de cola. Tan pronto como foo() ejecuta bar() como su acción final, bar() puede reutilizar la pila asignada de foo() en lugar de añadir una nueva (y aumentar el uso de memoria).

function foo() // hace algo... return bar(); // forma adecuada de llamada de cola }

Si aplicamos nuestras nuevas optimizaciones de memoria recursiva al “mundo real”, podríamos ver beneficios de rendimiento sustanciales para recorrer/manejar conjuntos de datos extremadamente grandes. Para la mayoría de nosotros, el JavaScript cotidiano que escribimos no se beneficiará necesariamente de estas llamadas de cola optimizadas. Sin embargo, supongamos que tenemos ante nosotros un problema específico que requiere recorrer un árbol de datos masivo. Un árbol de datos en el que cada nodo tiene asociada una cantidad sustancial de información y sobrecarga, ¿te suena familiar? Por supuesto que sí, es la maravillosa API que todos conocemos y amamos, ¡el DOM! Como desarrolladores, nuestros programas, nuestros jefes y nuestros clientes a menudo requieren que interactuemos con el DOM (piense en un algoritmo de recorrido de árbol) donde el rendimiento es primordial. Pues bien, ahora estamos mejor equipados para hacer frente a estas situaciones.

En el sitio web de Guillaume Lathoud aquí se puede encontrar un ejemplo de implementaciones recursivas y recursivas de cola del recorrido del DOM. En el artículo, Guillaume profundiza mucho, comparando varias métricas de rendimiento, como el número de llamadas recursivas, el tamaño de la pila, el tiempo, etc., con respecto a estrategias recursivas competidoras. Su artículo es sin duda el más completo que he visto hasta ahora sobre la recursividad de cola en JavaScript, y recomiendo encarecidamente su lectura. A continuación se muestra un fragmento del artículo en el que creamos una función que recoge todos los nodos de archivos JavaScript en el DOM, utilizando un enfoque recursivo - recursiveCall(), así como un enfoque recursivo de cola - tailRecursiveCall(). Intenta entender el código de abajo…

var js_file_node_list = []; var js_node_check = function(node) { if ((node.nodeName === '#text') && (node.textContent.indexOf('.js') > -1)) { js_file_node_list.push(node); } }; // Ejecuta recursivamente tu función en cada nodo function recursiveCall(node, myFunction) { myFunction(node); var childNodes = node.childNodes; for (var i = 0; i < childNodes.length; i++) { recursiveCall(childNodes[i], myFunction); } } // Tail Recursion function tailRecursiveCall(node, myFunction) { return (function sub(_node, _myFunction, _from_below) { if (!_from_below) { _myFunction(_node); if (_node.firstChild) return sub(_node.firstChild, _myFunction, false); } if (_node.nextSibling) return sub(_node.nextSibling, _myFunction, false); if (_node.parentNode) return sub(_node.parentNode, _myFunction, true); })(node, myFunction, false); }

Así que hemos cambiado nuestros programas a modo estricto, hemos ajustado nuestras funciones recursivas para que tengan la forma adecuada de llamada a la cola, e incluso hemos visto ejemplos. La parte final (y por ahora, la más difícil) es ejecutar nuestro código ES6 en un entorno que realmente pueda manejar la optimización de llamadas de cola, y aquí es donde nos encontramos con un pequeño obstáculo. La implementación de la recursividad de cola es una característica del motor de interpretación, por ejemplo, V8 en Chrome, mientras que la disponibilidad para ejecutar nuestra recursividad recién optimizada depende del compilador y no del lenguaje en sí.

La referencia más actualizada de la disponibilidad de llamadas de cola (además de todas las demás características de ES6) se puede encontrar aquí, y en el momento de escribir este artículo actualmente no hay ni un solo navegador que tenga una implementación. Sin embargo, esto no debería sofocar nuestro interés por las nuevas características del lenguaje/implementación. Si nos armamos con el conocimiento de los conjuntos de herramientas que pronto estarán a nuestra disposición, estaremos mucho más preparados para escribir código limpio y altamente optimizado, una característica de los grandes programadores.

Se trata de una característica apasionante para una implementación enormemente nueva de JavaScript, y con el tiempo nos vendrá de cola por todas partes. Mientras tanto, para empezar a utilizar otras características de ES6, recomiendo traceur y 6to5, que permiten escribir código ES6 y transpilarlo a código ES5 válido y utilizable.

*Además, si quieres ver un buen ejemplo de recursividad en el mundo real, búscalo en Google

*Lecturas adicionales: Aparte de la investigación de Guillaume Lathoud sobre la recursividad de cola, recomiendo encarecidamente echar un vistazo al taller JS.Next: ES6 de Aaron Frost en FrontEndMasters.com. Proporciona una gran visión general introductoria de las numerosas características de ECMAScript 6, y es principalmente lo que me inspiró para escribir este artículo

Chris Amatangelo es Ingeniero Web en DOOR3. Póngase en contacto con nosotros hoy mismo