Artículo: ¿Qué es la recursividad?

¿Qué es la recursividad?

En ocasiones nos encontramos con problemas aparentemente complejos de resolver programando al estilo “tradicional”, es decir utilizando bucles para repetir un código hasta que se cumpla una condición. Esta forma de programar se denomina programación iterativa, y como digo no siempre es la mejor para resolver cierto tipo de problemas.
En contraposición a la programación iterativa surge la denominada recursividad o programación recursiva, que consiste en aplicar al mundo de la programación la famosa frase de Julio Cesar "Divide et vinces" – Divide y Vencerás. La programación recursiva a menudo ofrece soluciones elegantes a problemas difíciles de resolver de otro modo, descomponiendo dichos problemas en otros más sencillos.

Una función recursiva (o método recursivo) es aquella que contiene invocaciones a sí misma, de manera que el problema se va descomponiendo en sub-problemas más fáciles de resolver.  Así, una llamada a una función recursiva puede generar una o más invocaciones a la misma función, que a su vez genera otras llamadas, y así sucesivamente hasta llegar a lo que se denomina el caso base.  El caso base es un problema tan básico que la función sabe resolver sin necesidad de volver a invocarse a sí misma.
Una función recursiva debe cumplir las siguientes condiciones:

• Asegurarse de que existe una condición de salida, en la que no se producen llamadas recursivas (el caso base).
• Asegurarse de que se cubren todos los posibles casos entre el caso base y los no-base.
• Cada llamada, si se trata de un caso no-base, conduce a problemas cada vez más pequeños que terminarán en el caso base.

Como la definición de una función recursiva puede resultar complicada de comprender, vamos a ilustrarlo con unos ejemplos para tratar de entenderlo mejor.

Cálculo del Factorial de un Número

Un ejemplo de algoritmo recursivo es el cálculo del factorial de un número. El factorial de un número es el resultado del producto de todos los números inferiores o iguales a él, empezando por el 1. Por ejemplo, el factorial de 4 (que se escribe 4!) es 3*2*1 = 6. Así, la definición recursiva del factorial podría estar compuesta por dos puntos:

El primer punto dice que el factorial de un número no es más que el mismo número multiplicado por el factorial de su número predecesor (el número menos uno). El segundo punto es el caso base, que dice que el factorial de uno es uno.
A continuación se muestra el código en Java de una función que es capaz de calcular el factorial de un número de manera recursiva (llamándose a sí mismo hasta llegar al caso base):

En el código anterior se puede ver cómo la función factorial se llama a sí misma con el número anterior al que se le ha enviado (línea 10), a no ser que el número sea uno, en cuyo caso se devuelve uno (línea 8).  Así, se van produciendo sucesivas invocaciones a la función hasta llegar al caso base.

Las Torres de Hanoi

Otro ejemplo clásico de algoritmo recursivo es la resolución del problema de Las Torres de Hanoi. Se trata de un rompecabezas inventado en  1883 por el matemático francés Éduard Lucas, que consiste en pasar una serie de discos de diferentes tamaños de una barra vertical situada a la izquierda a otra barra vertical situada a la derecha. Para ello se puede utilizar una barra auxiliar situada en el centro de las otras dos, con la única restricción de que nunca un disco de menor tamaño puede quedar por encima debajo de otro mayor.

Si pensamos en cómo resolveríamos este problema con un ordenador, la solución iterativa no es nada fácil de implementar. Sin embargo, una solución recursiva puede programarse con pocas líneas de código, según se muestra en la siguiente figura:

Fijándonos en el código, podemos ver como la función mover tiene dos llamadas recursivas. El caso base es cuando ya no hay que mover ningún disco, y cualquier caso no-base realiza tres pasos:

1. Mueve todas las piezas menos una a la barra temporal
2. Mueve la pieza que queda a la barra destino
3. Mueve todas las piezas que movió a la barra temporal a la barra destino

Con este sencillo algoritmo somos capaces de resolver un problema tan complejo como las torres de Hanoi con pocas líneas de código. La salida del programa para una torre de Hanoi de cuatro discos (aunque funciona para cualquier número) es la siguiente:

Backtracking: Cuando recursividad y fuerza bruta van de la mano

El backtracking, también conocido como “vuelta atrás”, es una técnica algorítmica de resolución de problemas mediante una búsqueda sistemática de soluciones. El backtracking hace uso de la recursividad para descomponer la tarea a realizar en tareas parciales, y probar cada una de estas. Cuando al elegir una tarea se comprueba que no lleva a ninguna solución, se debe volver atrás, y probar con otra. Así, se van probando sistemáticamente posibles soluciones al problema hasta que se encuentra una que lo resuelve.

Ejemplo de Backtracking: Resolviendo Laberintos

Un ejemplo de problema fácilmente resoluble con backtracking (y difícil sin métodos recursivos) es el encontrar la salida a un laberinto. El algoritmo básicamente funciona así:

1. Comprobamos si la casilla donde estamos actualmente ya es la salida, y si es así, salimos de la función indicando que se ha encontrado la casilla de salida.
2. Si no es así, entonces llamamos recursivamente a esta misma función con la casilla de arriba de la actual, y si ahí se encuentra la salida, salimos de la función indicando que se ha encontrado la salida del laberinto.
3. Si no se encontró la salida por arriba, entonces llamamos recursivamente a esta misma función con la casilla de abajo de la actual, y si ahí se encuentra la salida, salimos de la función indicando que se ha encontrado la salida del laberinto.
4. Si no se encontró la salida por abajo, entonces llamamos recursivamente a esta misma función con la casilla de la izquierda de la actual, y si ahí se encuentra la salida, salimos de la función indicando que se ha encontrado la salida del laberinto.
5. Si no se encontró la salida por la izquierda, entonces llamamos recursivamente a esta misma función con la casilla de la derecha de la actual, y si ahí se encuentra la salida, salimos de la función indicando que se ha encontrado la salida del laberinto.
6. Si no se encontró la salida por ninguna de las cuatro casillas colindantes, entonces salimos de la función indicando que no existe salida del laberinto por la casilla actual.

A continuación se muestra el código del algoritmo de resolución de laberintos:

Parece increíble que con estas pocas líneas de código se pueda encontrar la salida de cualquier laberinto,  independientemente de su complejidad (aunque no se asegura que sea la salida más corta). Al ejecutar el programa, obtenemos la salida del laberinto de ejemplo:

Otro Ejemplo de Backtracking: Resolviendo Sudokus

Otro clásico ejemplo para ilustrar el uso del backtracking es un programa que resuelve sudokus utilizando esta técnica. El algoritmo funciona básicamente así:

1. Elegir la primera casilla vacía, empezando a buscar desde la casilla superior izquierda.
2. Probar a colocar el número 1 en esa casilla, y ver si no existe ningún conflicto (no existe ningún número igual en la misma fila, columna o bloque):

• Si existe un conflicto, volver al paso 2) y probar con el siguiente número
• Si no existe ningún conflicto, llamar recursivamente al paso 1) para ver si se encuentra una solución:
• Si no se encuentra, y hay más números para probar, volver al paso 2) y probar con el siguiente número.
• Si no se encuentra y no hay más números para probar, salir de la función indicando que no se ha encontrado solución.
• Si se encuentra, salir de la función indicando que si se ha encontrado solución.

A continuación se muestra el código en Java del algoritmo para resolver cualquier Sudoku utilizando backtracking:

Al ejecutar el programa con el Sudoku de ejemplo se obtiene la solución en pocos segundos: