Torres de Hanoi.

   Existen varias versiones y variantes del problema de las torres de Hanoi, pero la versión clásica y más común es la siguiente:

Se tienen tres postes, normalmente denotados como A, B y C, y en uno de ellos (poste de origen, usualmente A) se tienen apilados n discos de diferentes diámetros. 

El problema consiste en pasar los n discos del poste origen al poste destino (usualmente C) manteniendo en todo momento las siguientes reglas:

1. Sólo se puede mover un disco cada vez.
2. Un disco de mayor diámetro no puede estar sobre uno de menor diámetro.
3. Sólo se puede mover el disco que se encuentre en la parte superior de cada poste.

   Ahora bien, para el caso de n = 1, si A es el poste origen, C el poste destino, y B el poste auxiliar, la solución es directa:

Mover el disco 1 del poste A al poste C.

   Para el caso de n = 2, si A es el poste origen, C el poste destino, y B el poste auxiliar, la solución está dada por los siguientes movimientos de discos, donde el disco 1 es el más pequeño y el disco 2 es el más grande:

Mover el disco 1 del poste A al poste B

Mover el disco 2 del poste A al poste C

Mover el disco 1 del poste B al poste C

   Para el caso de n = 3, si A es el poste origen, C el poste destino, y B el poste auxiliar, la solución está dada por los siguientes movimientos de discos, donde el disco 1 es el más pequeño y el disco 3 es el más grande:

Mover el disco 1 del poste A al poste C

Mover el disco 2 del poste A al poste B

Mover el disco 1 del poste C al poste B

Mover el disco 3 del poste A al poste C

Mover el disco 1 del poste B al poste A

Mover el disco 2 del poste B al poste C

Mover el disco 1 del poste A al poste C

   Para visualizar mejor la solución, se sugiere como ejercicio realizar los dibujos que reflejen la naturaleza de estos movimientos. Adicionalmente, se sugiere realizar la misma labor para cuatro y cinco discos. Hágalo antes de continuar.

   Si realizó lo sugerido en el párrafo anterior, quizá haya identificado algunos patrones:

• Para el caso de cuatro discos, se tiene la situación inicial sugerida por la siguiente figura:

• Para el caso de cuatro discos (en general para el caso de n discos), después de algunos movimientos se tiene la situación presentada en la siguiente figura, en la que se observan los n - 1 discos colocados en la posición auxiliar B, y el disco de mayor diámetro listo para ser movido a su posición final:

• El siguiente paso es el movimiento del disco de mayor diámetro de la posición origen A hacia su posición final de destino (C). Observe que los discos en la posición auxiliar no se afectan, como lo muestra la siguiente figura:

• Ahora bien, de la figura anterior puede notarse lo siguiente: en la posición B están los n - 1 discos restantes, es decir, el problema original de n discos pero simplificado (al menos por un disco), por lo que, si se toma como nuevo origen la posición B, se mantiene el destino en la posición C y se hace que la posición auxiliar sea ahora A, se tiene la misma situación del problema original pero con menos discos y con nuevos roles respecto a la posición de origen y la auxiliar.

   En resumen el problema se reduce ahora a mover los n - 1 discos de la posición B a la posición C utilizando a la posición A como auxiliar, y si se repite el procedimiento, se obtendrá eventualmente la situación presentada en la siguiente figura:

   De lo anterior se pueden deducir las relaciones de recurrencia y el caso base para dar solución recursivamente al problema de las torres de Hanoi. De manera general, se presenta a continuación el algoritmo de las torres de Hanoi:

Algoritmo mover_disco(n: entero, origen: character, destino: character, auxiliar: character)
Inicio
            if (n == 1)
                        imprimir mover el disco n de la posición origen a la posición destino
            else
                        mover_disco(n - 1, origen, auxiliar, destino)
                        imprimir mover el disco n de la posición origen a la posición destino
                        mover_disco(n - 1, auxiliar, destino, origen)
            end if
Fin

   Observe que el algoritmo anterior es una descripción en pseudo código de los patrones identificados en el texto. Por otro lado, si se realizó el ejercicio sugerido con anterioridad, un análisis cuidadoso deberá llevar al lector a la identificación de dichos patrones.

Consideraciones adicionales.

   En resumen, las implementaciones recursivas son en general ineficientes en tiempo y espacio, pero muy elegantes y simples una vez que se tiene identificada la relación de recurrencia. En este sentido, siempre que pueda identificar un enfoque iterativo que sea sencillo de implementar, opte por él.

   Por otro lado, el problema de las torres de Hanoi es un ejemplo ineludible de que por medio de la recursividad es posible solucionar problemas complejos de manera bastante sencilla, aunque el precio a pagar sea la eficiencia en tiempo y espacio de memoria. Intente resolver el problema de las torres de Hanoi de manera iterativa para tener una mejor comprensión de lo anterior, y experimente directamente y de primera mano el eterno conflicto (tradeoff) computacional entre espacio vs. tiempo, y eficiencia vs. simplicidad.

Ejercicios selectos (recursividad).

1. En la entrada Recursividad (Definición y conceptos), se presenta y describe brevemente una figura geométrica generada mediante un proceso recursivo potencialmente infinito. Siguiendo lo descrito en dicha entrada, dibuje en papel la figura geométrica correspondiente de Nivel 5.
2. Haga un análisis de los llamados y retornos recursivos como los realizados en la entrada "Soluciones iterativas vs. recursivas" para los llamados de función factorial(5) y factorial(6).
3. Escriba un programa que, a través de una función recursiva, calcule el producto de dos números enteros positivos a y b por medio de sumas sucesivas, esto es: a * b = a + a + . . . + a, donde a se suma tantas veces como lo indique b. Para este ejercicio, asuma que b siempre será positivo, la idea de toda esta sección es poner en práctica la recursividad más que el análisis de todos los casos posibles para a y b.
   
4. Realice en una hoja de papel el árbol de recursividad que se genera para el cálculo de fibonacci(5) y fibonacci(6) como el que  se mostró en "Soluciones iterativas vs. recursivas".
5. Escriba un programa que, a través de una función recursiva, calcule el cociente entero de dos números enteros positivos a y b por medio de restas sucesivas, esto es a / b ==>
1.   a - b = c1, si c1 >= b, entonces
2. c1 - b = c2, si c2 >= b, entonces
3. c2 - b = c3, si c3 >= b, entonces
4.         .     .     .                                         donde el cociente estará dado por el número de veces que se haya podido repetir el procedimiento descrito.
6. Escriba un programa que, a través de una función recursiva, calcule la potencia de dos números enteros positivos a y b por medio de productos sucesivos, esto es: a^b = a * a * .  .  . * a, donde a se multiplica tantas veces como lo indique b.
7. Compare las versiones recursivas con las versiones iterativas descritas en el blog y analícelas. Simplemente por la lectura del código, ¿qué versión representa una mejor abstracción de las definiciones matemáticas? Realice diferentes ejecuciones y determine qué versión tiene un mejor rendimiento.
8. Tanto el factorial como la serie de Fibonacci crecen de manera exponencial y no hay tipo de dato que las pueda contener. En el lenguaje de programación C, los tipos de datos numéricos dividen su rango tanto en números positivos como en números negativos, por lo que su capacidad de almacenamiento se ve, por decirlo de alguna manera, dividida. Sin embargo, existe el modificador unsigned (sin signo), que instruye al compilador para usar todo el rango de bits del tipo de dato para representar números positivos incluyendo el cero. Pruebe con este modificador de tipo de datos, documéntese en su funcionamiento y su especificador de formato, y amplíe la capacidad de representación para los resultados de los ejemplos estudiados en el blog.
9. En base a lo indicado en el ejercicio anterior, calcule con la versión iterativa y recursiva respectivamente, fibonacci(52), ¿qué observa? ¿qué puede deducir?
10. En base a lo expuesto en el blog y basándose en el Ejemplo 5.5, determine el tiempo en segundos que tarda la función de Fibonacci en determinar, por ejemplo, fibonacci(49) en sus respectivas versiones: iterativa y recursiva.
11. Escriba un programa que, en base al algoritmo descrito para las Torres de Hanoi, resuelva dicho problema por medio de una función recursiva. Note que es un proceso de simple traducción al lenguaje C, ya que tanto las relaciones de recurrencia, como el criterio de paro están dados en el algoritmo.
12. Basándose en el ejercicio anterior y en el Ejemplo 5.5, determine el tiempo en segundos que tarda la función que da solución al problema de las torres de Hanoi para 20, 35 y 50 discos por ejemplo.

Estructuras de control combinadas.

   A continuación se presenta un programa un poco más elaborado. El Ejemplo 3.17, utiliza la estructura de selección switch anidada dentro de una estructura de repetición while; también se utiliza la función getchar (línea 13), la cual regresa un carácter leído desde la entrada estándar.

   El prompt de la línea 11 indica que para terminar la entrada de datos se escriba EOF, el cual es un acrónimo de End Of File.

   Si los datos se procesan desde un archivo (y para este ejemplo es posible sin realizar cambio alguno en el código), la marca EOF se encontrará al final del mismo; pero si los datos se procesan desde el teclado, la marca de EOF tendrá que ser simulada: en GNU/Linux se simula con la combinación de teclas Ctrl+D, mientras que en Windows la combinación es Ctrl+Z.

   Observe la sentencia de la línea 13, la cual es un ejemplo muy usual de la forma de escribir expresiones y sentencias en C, ya que la expresión condicional del ciclo while está combinada con una expresión de asignación. La sentencia podría interpretarse en nuestro lenguaje como: “Obtén el siguiente carácter de la entrada estándar, asígnalo a simbolo, y si es distinto de EOF, ejecuta el grupo de sentencias del ciclo”.

   Note que la variable simbolo es de tipo entero (int). Esto se debe a que la función getchar regresa el número entero que representa al símbolo (carácter) procesado.

   Por otro lado, la estructura switch se encarga de hacer una comparación del dato contenido en simbolo, contra los casos (case) de interés: las vocales mayúsculas o minúsculas. Note también la forma en que se han expresado los casos (case), ya que no se ha hecho uso de ningún operador lógico (de hecho, intencionalmente no han sido presentados), pero las sentencias de las líneas 15, 16 y 17 podrían interpretarse en nuestro lenguaje como: “En caso de que simbolo sea una 'A'  o una 'a', incrementa el contador de a's y termina la comparación”. Las líneas 18-29 tendrían una interpretación análoga.

   Observe también que los símbolos 'A' y 'a' han sido puestos entre comillas simples, lo cual, además de auto documentar mejor el código fuente, sirve para que el compilador traduzca el código de dichos símbolos, en su correspondiente representación numérica, y puedan así ser comparados con el valor regresado por la función getchar.

   En resumen, la estructura while se encarga de repetir la lectura de datos y de enviarle los datos a la estructura switch mientras el dato procesado sea distinto de EOF; por otro lado, la estructura switch se encarga de determinar si el dato procesado es o no una vocal. Si lo es, la contabiliza en el contador correspondiente, y si no, lo ignora (default de la línea 30).

   Una muestra de la ejecución del Ejemplo 3.17 con datos procesados desde el teclado se muestra en la siguiente figura:

Una posible salida del Ejemplo 3.17.

 

   Hasta ahora ha sido posible resolver todos los ejemplos y ejercicios sin el uso de operadores lógicos, de hecho esa ha sido la intención, sin embargo, el uso de operadores lógicos resulta indispensable para resolver de manera más sencilla diferentes tipos de problemas. La tabla siguiente muestra los operadores lógicos en C.

Operador    Descripción

               &&          Conjunción (And)

              |  |           Disyunción (Or)

              !            Negación (Not)

   Finalmente, compare el Ejemplo 3.17 con el Ejemplo 3.17_1. Este último hace exactamente lo mismo que el primero pero con una estructura de control if-else anidada y muestra también el uso de los operadores lógicos dentro de una expresión de tipo condicional.