- 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
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.