Introducción

La recursividad es una de las claves dentro de la Programación Funcional y la algoritmia. Sin embargo, históricamente ésta ha resultado un problema cuando se aplicaba sobre Javascript debido a la gestión de recursos propia del lenguaje. Con el nuevo estándar ES6, y las mejoras introducidas, esta circunstancia queda resuelta al menos desde un plano teórico. Veamos exactamente en qué consiste tanto el problema como la solución aportada.

Recursividad y pilas

Para no andar con definiciones complejas que podemos consultar en la misma Wikipedia, podemos resumir que la recursión es el proceso por el cual un procedimiento (una función, un método…) se llama a sí mismo de forma periódica, generalmente, hasta que se cumple alguna condición que detiene el ciclo.

En Javascript, antes de la especificación ECMAScript 2015, cada vez que una función se llama así misma crea una nueva pila (traducción del término anglosajón ‘stack’). Esa pila permite al lenguaje mantener un registro o seguimiento de la información relacionada con la función en el momento de su ejecución tales como sus valores iniciales, argumentos, contexto, etc…

Una pila (stack en inglés) es una lista ordenada o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos.

Wikipedia, Pila (informática)

Este comportamiento derivaba en que funciones con una alta recursividad, creaban un igualmente alto número de pilas. Y eso era uno de los puntos débiles de Javascript: cada nuevo stack supone un coste de memoria limitado en última instancia por la disponible en el sistema. Dicho de otro modo: si un procedimiento recursivo se ejecutaba un número suficientemente alto de veces, la memoria del sistema se agotaba provocando un error. Los más veteranos seguro que reconocen ese error como uno de los más temidos en cualquier lenguaje de programación: el siempre maldito stack overflow.

En informática, un desbordamiento de pila (stack overflow/overrun) es un problema aritmético que hace referencia al exceso de flujo de datos almacenados en la pila de una función.

Ejemplo rápido del problema

Tomemos un fragmento clásico de recursividad: el cálculo de número factoriales. Para ello, recurrimos a un código publicado en la web para desarrolladores de Microsoft:

var counter = 0;
 
var factorial = ( num ) => {
    // Increment counter
    counter++;
 
    // If the number is less than 0, reject it.
    if ( num < 0 ) {
        return -1;
    }
 
    // If the number is 0, its factorial is 1.
    else if ( num == 0 ) {
        return 1;
    }
 
    // Otherwise, call this recursive procedure again.
    else {
        return ( num * factorial( num - 1 ) );
    }
}
 
console.info( factorial( 8 ) ); // 40320
console.info( counter ); // 9

NOTA: He añadido una variable de tipo contador (counter) para comprobar rápidamente las llamadas a la función principal.

Con un número pequeño como el del ejemplo (8) la función ‘factorial’ es lanzada 9 veces. Eso quiere decir que se han creado 9 pilas o stacks, las cuales permanecen dentro de los límites de la
memoria del sistema y se resuelven con éxito.

EL problema llega con números mayores y, en consecuencia, un mayor número de pilas:

console.info( factorial( 9999 ) ); // InternalError: too much recursion

El ejemplo anterior dispara el error; en este caso el motor interpreta que estamos en un bucle infinito (aunque en realidad la condición de salida existe) y para evitar el desborde, detiene el flujo.

NOTA: Para saber más sobre este error en concreto, podemos consultar su documentación al respecto en MDN aquí.

Optimización de cola – TCO

Para solucionar este problema, ES6 ha incorporado la TCO en su definición.

La optimización de cola o TCO es un proceso por el cual un compilador inteligente realiza llamadas a una función sin necesidad de crear una nueva pila. Para que esto sea posible, tiene que cumplirse una condición básica: que la última instrucción que se ejecute en dicha función (llamémosla ‘f’) sea una llamada a otra función ‘g’ (aunque ‘g’ sea igualmente ‘f’).

Como la mayoría de definiciones, esta puede resultar confusa pero únicamente quiere decir que la función debe siempre terminar llamando a otra función. Esa función ‘auxiliar‘ puede a su vez volver a llamar a la anterior o simplemente ser una referencia a la misma. Cuando esta condición se cumple, decimos que la llamada a la función está en la cola y que por tanto es optimizable.

Con un ejemplo sencillo sobre nuestro ejercicio ‘factorial‘ podemos intentar aclararlo:

var factorial = ( num ) => {
    return facRec( num, 1 );
};
 
var facRec = ( x, acc ) => {
    if ( x <= 1 ) {
        return acc;
    } else {
        return facRec( x-1, x * acc );
    }
};
 
console.info( factorial( 8 ) ); // 40320

La clave aquí es cómo la última instrucción de la función ‘factorial’ es una llamada a la auxiliar ‘facRec‘ (por tanto, ‘está en la cola’). Desde esa nueva función, en caso de cumplir la condición de recursividad, volvemos a llamar a ‘factorial‘. Este fragmento es por tanto válido y optimizable para el motor Javascript.

Quizá podemos encontrar poco estético el necesitar de un par de funciones para realizar un cálculo… y de hecho lo es. Más adelante optimizaremos un poco el código anterior para evitarlo, pero de momento ilustra perfectamente la idea.

La importancia del retorno

Consideremos por un momento que la función factorial del ejemplo anterior quedara como sigue:

var factorial = ( num ) => {
    facRec( num, 1 );   
};

Nótese que hemos omitido la instrucción ‘return‘. Como bien sabemos, si en Javascript omitimos el retorno, el motor lo añade por su cuenta (toda función debe devolver una salida). Es por ello que ‘factorial‘ se transforma silenciosamente en:

var factorial = ( num ) => {
    facRec( num, 1 );   
 
    return undefined;
};

Y ahora ya no sigue el principio de optimización de cola. El motivo es que en esta ocasión, la última instrucción no es la llamada a la función auxiliar, sino el retorno. Y como vimos antes, esa condición es la clave del TCO.

Expresiones que habilitan el TCO

Las Funciones Flecha permiten expresiones como cuerpo, lo cual posibilita el uso de TCO siempre y cuando éstas estén en la posición correcta (última instrucción ejecutada). Las expresiones que permiten esta estructura son:

El operador ternario

var myFunc = x => x ? foo() : bar();

En la función anterior, tanto ‘foo‘ como ‘bar‘ serían la última instrucción a ejecutar dependiendo de la condición ‘x‘. Es por ello que ‘myFunc‘, es optimizable.

NOTA: Para saber más sobre el operador ternario, se puede consultar la correspondiente entrada en este blog aquí.

Los operadores lógicos AND y OR

var myFunc = () => foo() || bar();

En esta ocasión, ‘foo‘ no está en la cola, pero sí lo está ‘bar‘. La razón es que ‘foo’ se lanza para inmediatamente pasar a evaluar su resultado en el condicional implícito de OR. En el caso de un valor de tipo falsy, la llamada a ‘bar‘ sí resulta en la última instrucción y, por tanto, si sería optimizable. Queda más claro si desarrollamos el código anterior:

var myFunc = () => {
    var result = foo();
 
    if ( result ) {
        return result;
    } else {
        return bar();
    }   
}

Ocurre de forma similar con el operador AND:

var myFunc = () => foo() && bar();

De nuevo ‘foo‘ no está en la cola mientras ‘bar‘ sí lo está. Si volvemos a desarrollar el condicional abreviado resulta más claro:

var myFunc = () => {
    var result = foo();
 
    if ( ! result ) {
        return result;
    } else {
        return bar();
    }   
}

EL operador coma

Tratado recientemente en este mismo blog, ya estudiamos cómo el operador coma permite encadernar varias expresiones devolviendo el valor de la última:

var myFunc = () => ( foo(), bar() );

El desarrollo del código anterior nos permite ver cómo ‘foo‘ no está en la cola a diferencia nuevamente de ‘bar‘ que sí lo está:

var myFunc = () => {
    foo();
 
    return bar();
}

Optimización

Es importante reiterar que la última instrucción de una función optimizable debe ser la llamada a otra función; cualquier expresión que compute sobre el valor devuelto no sería válido:

var factorial = ( num ) => {
    if ( num <= 1 ) {
        return 1;
    }
 
    return num * factorial( num - 1 );
}

Esta función no es optimizable dado que la última instrucción no es la llamada a otra función, sino la expresión que multiplica el valor devuelto por el valor de ‘num‘. Eso impide al motor suprimir la pila obligándole a crear una nueva donde se almacenen los valores iniciales.

Para convertir esta función en una optimizable por el compilador, solo tenemos que eliminar la expresión:

var factorial = ( num, acc = 1 ) => {
    if ( num <= 1 ) {
        return acc;
    }
 
    return factorial( num - 1, num * acc );
}

Con esta modificación, la expresión se traslada a la propia función que ahora recoge un valor al que denominamos ‘acumulador‘ (acc). Este valor es una forma elegante de evitar esa partición en dos de la función que vimos en el primer ejemplo.

Ejemplos interesantes de recursividad optimizada

Los siguientes ejemplos están tomados de la web 2ality y suponen un buen ejercicio de funciones recursivas optimizadas:

var forEach = ( arr, callback, start = 0 ) => {
    if ( 0 <= start && start < arr.length ) {
        callback( arr[ start ], start, arr );
 
        return forEach( arr, callback, start + 1 );
    }
};
 
forEach( 
    [ 'la', 'donna', 'e', 'mobile' ], 
    ( ele, i ) => console.info( ele.toUpperCase() ) 
);
 
// LA
// DONNA
// E
// MOBILE

La clave de este ejemplo está en que la última instrucción es la llamada así mismo (a través de return) y el acumulador ‘start‘ que hace innecesario el almacenamiento de los valores en la pila.

var findIndex = ( arr, predicate, start = 0 ) => {
    if ( 0 <= start && start < arr.length ) {
        if ( predicate( arr[ start ] ) ) {
            return start;
        }
 
        return findIndex( arr, predicate, start + 1 );
    }
}
 
findIndex( 
    [ 'la', 'donna', 'e', 'mobile' ], 
    x => x === 'mobile' 
); 
 
// 3

Estructura similar y, por tanto, optimizable de igual modo.

TCO y el strict mode

Un aspecto importante a destacar es que, la optimización de cola solo está disponible en el modo estricto. Esto es así porque en el modo ‘no estricto’, el motor de Javascript asocia de forma automática dos propiedades ocultas a cada función: arguments y caller. El primero almacena en un pseudo array los argumentos con los que la función ha sido llamada mientras que el segundo hace referencia a la función ejecutada inmediatamente antes (y que suele corresponderse con la que ha llamado a la actual).

Estas dos propiedades impiden al motor eliminar la pila actual obligándole a crear una nueva por cada iteración. Dado que en el modo estricto ambas están prohibidas, se evita el problema.

Compatibilidad

A fecha de redacción de este artículo (octubre de 2016), la optimización de cola solo está parcialmente implementada en los principales navegadores web:

Safari (TP) va por buen camino, mientras que Chrome (v53 y v54) requieren de un ‘flag‘ para su uso. Firefox, por su parte, aún no lo soporta.

Babel: primero sí, ahora no.

Un caso especial lo tenemos con Babel, el popular transpiler para ES6. Si bien se incorporó inicialmente un sistema TCO para la versión 5, por dificultades y bugs imprevistos se deshabilitó de forma temporal en la v6:

Only explicit self referencing tail recursion was supported due to the complexity and performance impact of supporting tail calls globally. Removed due to other bugs and will be re-implemented.

Babel
Learn ES2015

Actualmente, no existe ningún plugin que re habilite esta funcionalidad en la célebre biblioteca.

Conclusión

La recursión es una herramienta poderosa (clave dentro de la programación funcional) que históricamente ha exigido de un fuerte diseño (y malabares) en Javascript dadas sus limitaciones de memoria. Con ES6, se han introducido en la especificación los mecanismos necesarios para permitir al compilador su optimización y, con ello, un aprovechamiento inteligente de los recursos del sistema.

Si bien a día de hoy su soporte está aún muy limitado, podemos desde ya planificar nuestros algoritmos con este comportamiento en mente. Basta con asegurarnos de que nuestras llamadas a funciones se encuentran en la cola de optimización tal y como hemos ido viendo en los ejemplos anteriores.

Para saber más:

Standard ECMA-262
6th Edition / June 2015
ECMAScript® 2015 Language Specification
http://www.ecma-international.org/ecma-262/6.0/#sec-tail-position-calls