En ningún momento quiero dar la impresión de que la recurisividad en programación sea intrínsecamente mala. Nada más lejos de mi intención.

La recursividad en la programación es una herramienta fantástica para expresar muchos algoritmos de manera sencilla. Nos sirve para experimentar con facilidad, resolver muchos problemas de manera sencilla y elegante, demostrar propiedades acerca de los algoritmos y un montón de cosas más. Pienso sinceramente que su dominio por parte de cualquier programador es imprescindible. Grandes desarrollos en el campo de los compiladores, los fractales, la compresión de datos...y un sinfín más hubieran sido mucho más difíciles sin una primera aproximación recursiva.

Pero desde el punto de vista de un entorno productivo, es decir, cuando se requiere una explotación de una aplicación de una manera lo más segura y eficiente posible, la recursividad suele presentar una gran ineficiencia, y el peligro inherente y difícilmente controlable de un desbordamiento de pila. En estos entornos, si hemos utilizado recursividad durante el desarrollo es altamente recomendable obtener una solución iterativa equivalente para la versión en producción, que podremos controlar con mucha mayor eficacia.

Esta solución iterativa se puede lograr siempre. En algunos casos sencillos (como los que hemos visto del factorial o de la sucesión de Fibonacci) basta con dedicar un pequeño análisis al significado de la función para encontrar una serie de pasos repetitivos que nos lleven a la solución.

Estos casos son sencillos de resolver porque nos podemos dar cuenta de que la cantidad máxima de información (dicho de otro modo, de memoria, de variables locales y parámetros) que necesitamos para resolver el problema en un instante dado está perfectamente acotada, y a medida que vamos solucionando casos nuevos, podemos ir descartando la solución de casos antiguos. Por ejemplo, en la sucesión de fibonacci sólo necesitamos en un instante dado conocer los dos casos anteriores... por eso para calcular fib(6) empezamos por fib(1) y fib(2), y cuando calculamos fib(3) nos deshacemos de fib(1), porque no lo volveremos a necesitar... cuando calculamos fib(4) nos deshacemos de fib(2)... y asi hasta llegar a fib(6). Sólo necesitamos fib(4) y fib(5). (Estos son esquemas de problemas en los que podemos aplicar programación dinámica)

Existen no obstante otros problemas que tienen solución recursiva en los que esta cantidad máxima de memoria necesaria no puede acotarse... Es decir... no podemos "deshacernos" de porciones de información, y quedarnos sólo con las últimas generadas. En ese caso, podemos aplicar una transformación recursivo-iterativa metódica. En estas transformaciones, lo que hacemos es sustituir las llamadas recursivas por un bucle y una estructura dinámica de tipo pila. Esa bucle y la estructura deben sustituir al trabajo que hace la pila de llamadas durante la recursión. Al construir una pila con memoria dinámica, podemos controlar en todo momento su tamaño y otras propiedades, cosa que no ocurre con la pila de llamadas... pero de eso hablaremos en otro artículo.