Como no aprender sobre recursividad

A mediados de los 80s descubrí el fascinante mundo de la recursión gracias al lenguaje LOGO. LOGO es un lipsoide con excelente soporte gráfico, por lo que nada mas natural que combinar gráficos y recursión para generar fractales como el copo de nieve. Desgraciadamente la fuente de la que aprendí no era muy buena es ese tópico en particular. Los ingredientes en una función recursiva son:

• Un segmento de código que evite la recursión infinita
• Un segmento de código que haga el trabajo
• Un segmento de código que reinvoque la función

Con esta receta me encaminé a implementar mis propias funciones recursivas como la curva de Hilbert. Pasar de la teoría a la práctica es bastante difícil, sobre todo cuando no se tiene computador, mucho menos una versión de LOGO a la mano. Así que tenía que hacer los algoritmos en papel, hacer una corrida en frío, ejecutándolos con lápiz y escuadra. Pero la mayor dificultad estaba en dar con el algoritmo recursivo correcto, básicamente por ensayo y error.

Cuando pasé de los gráficos a las estructuras de datos, la vieja receta aprendida se mostró igualmente ineficiente. La recursión era para mí un arte y no una ciencia. Eso hasta que fui enseñado correctamente, gracias a un libro de Paul Graham.

La belleza de las funciones recursivas se muestra en todo su esplendor con las estructuras de datos recursivas. Cuando se define una estructura de datos recursiva se da una receta para crear nuevos valores en base a valores previos. Por ejemplo, para definir una lista en Haskell:

data Lista a = Nulo | Cons a (Lista a)

Esta expresión dice que una lista de un tipo "a" es o bien el elemento especial "Nulo" o la unión ("Cons") de un elemento de tipo "a" con una lista de tipo "a" (desde luego, Haskell ya tiene definido su propio tipo para las listas, con una notación mas suscinta. Sin embargo, para fines didácticos esta definición es mas conveniente).

Aquí es donde se evidencia el poder de las funciones recursivas. Para definir una función recursiva sobre el tipo de datos Lista a, solo hay que considerar que se debe hacer para cada una de las partes que conforman su definición. Donde aparezca "Lista a" cabe esperarse que haya un llamado recursivo. Por ejemplo, para obtener la longitud de una lista:

longitud Nulo = 0
longitud Cons a b = 1 + longitud b

Es esta simetría entre la forma de la estructura de datos y la función recursiva lo que facilita el trabajo al programador.