Recursividad con C# (2)

Como lo prometido es deuda, empezaremos esta segunda parte del minicurso de Recursividad en C# con el clásico Hanoi, y luego hablaremos sobre algunas técnicas asociadas al uso de la recursividad, como son “Backtracking” y “Divide y Vencerás”. Además, resolveremos paso a paso varios de los clásicos problemas de recursividad.

Según mi profesor de programación (Dr. Miguel Katrib), el juego de las torres de Hanoi es el poder expresivo de la Recursividad, y creo no hay mejor ejemplo que este para empezar a comprender como verdaderamente funciona la recursividad en C#.

El juego consiste en ir moviendo discos de la torre original de la izquierda de modo tal que finalmente queden en la misma posición en la torre de la derecha. Los movimientos de los discos deben hacerse bajo las siguientes restricciones: solo podrá moverse un disco a la vez y nunca podrá ubicarse un disco de mayor diametro sobre uno de menor diametro. La torre del centro puede utilizarse de modo auxiliar para el traspaso de los discos.

En la imagen de la derecha se muestran los movimientos a realizar para mover 3 discos. ¡Imaginen ahora la cantidad de movimientos a realizar para mover 10 discos! Lo que se quiere es un algoritmo que nos diga los movimientos a efectuar para mover una cantidad “n” de discos.

Analicemos ahora el problema:

1- Si la cantidad de discos a mover es 1, entonces movemos el disco de la torre de origen a la torre de destino.
2- Supongamos que sabemos mover n-1 discos desde la torre de origen hasta la torre auxiliar del centro.
3- El tercer paso consiste en mover el disco mayor que ha quedado solo en la torre izquierda hacia la torre de destino.
4- Mover esos n -1 discos desde la torre auxiliar (que hace de origen) hacia la torre de la derecha.

¿Cómo sabemos mover n-1 discos?

Como se podrá notar, este algoritmo se utiliza a si mismo y está basado en el principio de inducción matemática. Además, si no cree que podamos mover n-1 discos, entonces veamos si podemos mover n-2 discos, si tampoco lo cree podemos seguir hasta que tengamos que suponer que sabemos mover 1 disco, lo cual es cierto.

El método Mover a continuación escribirá como salida los movimientos a realizar para mover una cierta cantidad de discos que se le indica como primer parámetro. Los restantes parámetros serían los nombres de las torres de origen, auxiliar y destino.

De modo que cuando haríamos algo como:

La salida sería:

Seguro notaste que cada vez que se hace una llamada recursiva, la cantidad de discos que se pasa como primer parámetro disminuye en 1. De modo que en algún momento la cantidad de discos será 1, y entonces ya no se hará más ninguna llamada recursiva y el método Mover sabrá retornar a quién lo llamó.

Es C# quien lleva todo este proceso de saber como regresar y quien garantiza que los parámetros tengan los mismos valores que tenían antes de haberse hecho la llamada. Si todavía desconfía del trabajo recursivo, intente manualmente seguir el rastro de una llamada original a mover 4 discos.

Estrategia de “Divide y Vencerás”

Una estrategia importante en la recursividad es la llamada “Divide y Vencerás”. La implementación de soluciones basadas en esta estrategia no sería posible sin la recursividad. Dar un concepto de esta técnica o estrategia no es tan complicado. Primero veamos un ejemplo.

Busqueda Binaria

Considere que los elementos de un array de números enteros están ordenados de menor a mayor, por ejemplo {2, 3, 5, 7, 9, 12, 15, 18, 20}. Se quiere saber si el elemento 17 está en el array.

Lo que haremos será buscar el elemento que está en la mitad del array (9 en este caso). Si el elemento que buscamos es igual a este, hemos terminado. De lo contrario, como los elementos del array están ordenados, si el elemento buscado es mayor que el del medio, buscamos a la derecha, si es menor, a la izquierda. En este caso 17 es mayor que 9, y por tanto hay que buscar en {12, 15, 18, 20}. Ahora hacemos lo mismo, en este caso, hay que tomar una decisión, ya que como la cantidad de elementos es par, hay que ver si tomamos como el elemento del centro, el de más a la izquierda o el de más a la derecha (el 15 o el 18). Por ahora lo haremos con el que esté en el centro más a la izquierda (el 15). Como 17 es mayor que 15 buscaremos entonces en {18, 20}. El del medio es el 18. Y como el 18 es mayor que 17, entonces buscaremos en {18}. El elemento medio es el propio 18 que no es igual a 17. Como ya no se puede seguir haciendo subdivisiones, entonces podemos concluir que 17 no está en el array.

Por lo que el código sería el siguiente:

Note como, además de cumplir las 4 reglas de la recursividad, el método recursivo contiene dos llamadas recursivas que se aplican a dos posibles “divisiones” del problema original. Generalmente se considera que los algoritmos que contienen más de dos llamadas recursivas son algoritmos de “Divide y Vencerás”.

Podemos resumir entonces que esta estrategia consta de dos partes.

1- La división. Es donde el problema se divide en problemas más pequeños que a su vez re resuelven recursivamente.
2- La solución del problema original se forma a partir de estos problemas más pequeños.

Hasta aquí la segunda entrega de este tutorial sobre recursividad. De seguro, tienen un poco de dolor de cabeza.

En la tercera parte estaremos hablando de Backtracking (Vuelta atrás), y resolveremos otros problemas asociados con esta otra herramienta de la recursividad.

Para practicar con la estrategia “Divide y Vencerás”, pueden intentar hacer el algoritmo de “Ordenación por mezcla” (Mergesort) recursivo y “Subsecuencia continua de mayor suma”. Trataré de colgar las respuestas de estos algoritmos un poco más adelante.

Si tienen alguna duda o no entienden algo, deje su comentario.