Este artículo del blog explora una técnica para transformar código recursivo, a menudo elegante y mantenible, en una forma imperativa más robusta, especialmente útil en entornos como Node.js y TypeScript donde los desbordamientos de pila son una preocupación. La idea central es simular explícitamente la pila de llamadas del lenguaje, representando los marcos de pila como valores de primer nivel. Esto se logra utilizando registros mutables, un enfoque que, aunque no es automatizable, es principalmente mecánico y produce implementaciones relativamente comprensibles.
El artículo comienza explicando el problema con ejemplos sencillos: la suma de una lista enlazada y la suma de un árbol binario. La recursión, aunque clara, puede provocar desbordamientos de pila con estructuras de datos grandes. La solución iterativa, aunque funcional, elimina la necesidad de recordar cálculos parciales, lo que la hace más segura en términos de pila. Se ilustra cómo la conversión de una función recursiva a una iterativa implica el uso de estructuras de datos como punteros o pilas para simular el comportamiento de la pila de llamadas.
Un ejemplo más complejo involucra una estructura de datos mutuamente recursiva (árbol y bosque), que es inherentemente difícil de comprender y, por lo tanto, difícil de implementar iterativamente desde cero. La técnica presentada permite generar una solución iterativa incluso sin una comprensión profunda del problema, simulando la pila de llamadas para gestionar la ejecución paso a paso. La pila en la solución iterativa cumple la misma función que la pila de llamadas del lenguaje en la versión recursiva.
En esencia, el artículo propone una forma de 'relocalizar' la responsabilidad de la gestión de la pila de llamadas, pasando de ser una característica implícita del lenguaje a una gestión explícita por parte del programador. Esto implica un compromiso entre la claridad del código recursivo y la seguridad de la pila, así como una ligera penalización en el rendimiento. La técnica es adaptable a otros lenguajes con soporte para mutabilidad y polimorfismo paramétrico, aunque la implementación específica puede requerir ajustes dependiendo de las características del lenguaje.