La recursividad

La recursividad o recursión (en inglés, recursion) es la manera de resolver un problema reduciéndolo a otro igual pero más pequeño, y ese a otro más pequeño todavía, hasta llegar a uno tan simple que la respuesta es inmediata. En programación, se dice que una función es recursiva cuando se llama a sí misma. El ejemplo de manual es el factorial: el factorial de 5 es 5 por el factorial de 4, el de 4 es 4 por el de 3, y así hasta el factorial de 1, que es 1 sin más cálculo. Escrito como programa, son dos líneas: si n es 1, devolver 1; si no, devolver n por el factorial de n − 1.

Toda función recursiva que funciona tiene esas dos piezas. El caso base (base case) es el problema que se resuelve sin volver a llamarse, y el caso recursivo (recursive case) es el que se reduce a una versión más pequeña. Si falta el caso base, o si el caso recursivo no acerca el problema a él, la función se llama a sí misma sin fin. Es la versión informática del dibujo de Escher en el que dos manos se dibujan una a otra, y de la broma que Google mantiene desde hace años: al buscar recursion en su versión inglesa, el buscador pregunta «¿Quisiste decir: recursion?».

El problema que mejor muestra su fuerza son las torres de Hanói, un rompecabezas que el matemático francés Édouard Lucas puso a la venta en 1883. Hay tres varillas y una pila de discos de tamaños distintos ensartados en la primera, del mayor abajo al menor arriba, y hay que llevarlos todos a la tercera moviendo un disco cada vez y sin poner nunca uno grande encima de uno pequeño. Pensado de frente, es un laberinto. Pensado de forma recursiva, es trivial: para mover una torre de n discos, se mueve la torre de los n − 1 de arriba a la varilla auxiliar, se mueve el disco grande a su destino y se vuelve a poner encima la torre de n − 1. Cómo se mueve la torre pequeña no hace falta pensarlo, porque es el mismo problema con un disco menos. De ahí sale también la cuenta: hacen falta 2ⁿ − 1 movimientos, 7 con tres discos, 1.023 con diez y, con los sesenta y cuatro de la leyenda que Lucas inventó para promocionarlo, más de dieciocho trillones, que a un movimiento por segundo son casi seiscientos mil millones de años.

Muchos de los algoritmos más eficientes siguen el mismo patrón, que se llama divide y vencerás (divide and conquer). La búsqueda binaria busca en una lista buscando en su mitad; la ordenación por mezcla, uno de los algoritmos de ordenación más usados, ordena una lista ordenando sus dos mitades y mezclándolas. Y hay estructuras de datos que son recursivas por naturaleza: un árbol binario de búsqueda es un nodo con dos árboles más pequeños colgando, una carpeta de un ordenador contiene ficheros y otras carpetas, un documento HTML es una etiqueta que contiene etiquetas. Recorrerlas con una función recursiva es lo natural, porque el programa tiene la misma forma que los datos.

Por debajo, el ordenador lleva la cuenta con la pila de llamadas (call stack). Cada vez que una función llama a otra, o a sí misma, se apila un bloque de memoria con sus variables y el punto al que hay que volver; cuando termina, se desapila. Una recursión de profundidad mil deja mil bloques apilados a la vez. La pila tiene un tamaño fijo, y si se llena el programa se detiene con un desbordamiento de pila (stack overflow), el error que dio nombre al foro de preguntas más usado por los programadores. Por eso una recursión demasiado profunda es un fallo real y no teórico, y por eso algunos lenguajes aplican la optimización de llamada de cola (tail call optimization): si la llamada recursiva es lo último que hace la función, no hace falta guardar nada, y el compilador la convierte en un bucle.

El otro peligro es repetir trabajo. La definición de la sucesión de Fibonacci es recursiva, cada término es la suma de los dos anteriores, pero programada tal cual calcula el mismo término una y otra vez: el término cuarenta exige más de trescientos millones de llamadas. La solución es guardar cada resultado la primera vez que se calcula y consultarlo después, una técnica que se llama memoización (memoization) y que convierte ese cálculo exponencial en uno lineal, como explica la notación O grande.

La recursividad no siempre estuvo permitida. Los primeros lenguajes, como FORTRAN, no la admitían, porque guardaban las variables de cada función en un sitio fijo de la memoria y una segunda llamada pisaba la primera. En 1960 llegó por dos vías a la vez. John McCarthy la puso en el centro de LISP, un lenguaje pensado para la inteligencia artificial en el que las funciones recursivas eran la forma principal de programar, y el comité de ALGOL 60 la admitió en su lenguaje casi a última hora, contra la opinión de parte de sus miembros. Ese mismo año, Edsger Dijkstra publicó cómo implementarla con una pila, que es la solución que usan todos los procesadores desde entonces. Hoy la admite cualquier lenguaje, y los lenguajes funcionales, herederos de LISP, prescinden de los bucles y hacen todo con ella.

Pensar de forma recursiva exige una confianza que al principio cuesta: dar por resuelto el problema más pequeño sin comprobar cómo se resuelve. Los profesores de programación lo llaman el acto de fe recursivo. Una vez que se acepta, problemas que parecían exigir un plan completo se reducen a dos preguntas: cuál es el caso más simple, y cómo se pasa de un caso al siguiente.