Este artículo explora una idea contraintuitiva en programación: a veces, la mejor solución para un problema recursivo es, precisamente, una solución recursiva. La premisa central es que, aunque teóricamente cualquier función recursiva puede convertirse en una iterativa, esta transformación a menudo introduce una complejidad innecesaria y dificulta el mantenimiento del código.
El artículo ilustra esto con el ejemplo de un recorrido de un árbol binario para convertirlo en una lista enlazada. Se presentan implementaciones recursivas tanto para un recorrido preorden (visita el nodo actual primero) como para un recorrido postorden (visita el nodo actual al último). La belleza de las soluciones recursivas radica en su similitud: un pequeño cambio en los requisitos (invertir el orden del recorrido) resulta en una modificación mínima en el código. Esto demuestra una alta cohesión entre el código y la especificación del problema.
En contraste, la implementación iterativa del recorrido preorden se vuelve significativamente más compleja. Requiere el uso explícito de una pila para simular la pila de llamadas recursivas, lo que introduce detalles de implementación que no son inherentes al problema en sí mismo. Esta complejidad adicional, denominada 'incidental complexity', dificulta la comprensión del código y lo hace más frágil ante cambios en los requisitos. Si se necesitara una implementación iterativa del recorrido postorden, el cambio sería mucho más drástico, requiriendo una reescritura casi completa del código.
El artículo también menciona la existencia de soluciones iterativas con una o dos pilas para el recorrido postorden, pero enfatiza que estas soluciones son tan diferentes de la implementación preorden que no ofrecen ninguna ventaja en términos de mantenibilidad. La conclusión principal es que, cuando se trabaja con estructuras de datos recursivas, como los árboles, la correspondencia entre la implementación y la especificación del problema es crucial para la mantenibilidad y la adaptabilidad del código. En otras palabras, si la estructura de datos es inherentemente recursiva, la solución también debería serlo, para evitar la introducción de complejidad innecesaria y facilitar la adaptación a futuros cambios.