3.1.4 Un primer ejemplo: las torres de Hanoi

Pues bien, la magia debe comenzar. Para ello se recurrirá al algoritmo que se desarrolló en el tema anterior:

Resuelve TH (N, Fuente, Libre, Destino)
Si N es 0
Ningún movimiento
De otro modo
Resuelve(N - 1, Fuente, Destino, Libre)
Mueve Fuente = > Destino
Resuelve(N - 1, Libre, Fuente, Destino)

Figura 1. Historia de los lenguajes de programación

Sorprende lo fácil que es programarlo en Scheme. Las siguientes líneas constituyen un programa que resuelve el problema de las torres de Hanoi:

(define (resuelve-hanoi N fuente libre destino)

cond ((> N 0)

(resuelve-hanoi (- N 1) fuente destino libre)

(display "Moviendo disco ") (display (- N 1))

(display " de: ") (display fuente)

(display " -> ") (display destino) (newline)

(resuelve-hanoi (- N 1) libre fuente destino))))

La primera línea es casi idéntica, salvo por detalles como el orden y los paréntesis. Las siguientes tres son la parte condicional que pregunta si ya no hay discos que mover, eso mismo hace el cond en el programa (cond es abreviatura de conditional). Obsérvese la parte fundamental del algoritmo, esto es, las últimas cuatro líneas: en primer lugar está Resuelve(N - 1, Fuente, Destino, Libre), la primera llamada recursiva que resuelve las torres de Hanoi para los primeros N – 1 discos y en nuestro programa casi idéntica a (resuelve-hanoi (— N 1) fuente destino libre), salvo por los paréntesis y detalles como comillas o el orden N – 1 en vez de – N 1. Lo mismo sucede con la última línea, que es la segunda llamada recursiva. Esto plantea el problema de descifrar qué hace:

(display "Moviendo disco") (display (- N 1))

(display " de: ") (display fuente)

(display " -> ") (display destino) (newline)

Que es esencialmente lo mismo que: Mueve Fuente => Destino del algoritmo original. Lo único que hacen esas tres líneas es desplegar en la pantalla el movimiento que se realiza, que es también la tarea de Mueve en el algoritmo. Aquí va una ejecución del programa en acción. Primero, se teclea el siguiente comando al intérprete de Scheme (más adelante se describirá en detalle):

> (resuelve-hanoi 3 'A 'B 'C)

Entonces la computadora responde con el resultado de ejecutar el programa:

Moviendo disco 0 de: A -> C

Moviendo disco 1 de: A -> B

Moviendo disco 0 de: C -> B

Moviendo disco 2 de: A -> C

Moviendo disco 0 de: B -> A

Moviendo disco 1 de: B -> C

Moviendo disco 0 de: A -> C

Nótese que se han marcado en negritas las líneas que indican movimientos finales de discos a la torre de destino, es decir, C. Ya se había dicho que bastaba decir A –> C para indicar que se debe mover el disco más pequeño de la torre A a la C. Aquí, sin embargo, se imprime el número de disco para facilitar la lectura, cero (0) es el más chico y dos (2) en este caso el más grande.

Fue muy fácil, ¿no es así? Sin embargo, se dieron por sentado algunos detalles de programación que se explicarán posteriormente. Vamos a ubicar y referir algunos de esos detalles. Por principio de cuentas, todas las palabras en negritas son palabras del lenguaje Scheme con un significado fijo, llamadas palabras reservadas; algunas son procedimientos primitivos como – (resta) o display (que imprime algo en la pantalla); otras son expresiones de control o formas especiales, como define (definición de variables o procedimientos) o cond (forma condicional).

Ahora se desarmará el programa para señalar los detalles del lenguaje: (define (resuelve-hanoi N fuente libre destino)), define un procedimiento (o programa) que se llama resuelve-hanoi. Este procedimiento recibe cuatro argumentos: el número de discos, N, así como tres torres (fuente, libre y destino). Una vez definido un procedimiento, se puede ejecutar; esto se hizo después con: (resuelve hanoi 3 'A 'B 'C). Nótese que antes había un símbolo >, que se conoce como prompt y que es la forma del intérprete del lenguaje para indicar que está listo para recibir instrucciones y ejecutarlas.

Todo lo que sigue después de la primera línea se conoce como el cuerpo del procedimiento. Usualmente se utiliza una combinación de instrucciones de control y expresiones en estas definiciones. En el programa de las torres tenemos una expresión única formada por la estructura de control, cond. En el procedimiento se puede traducir como: "Si el disco que manejamos no es el más pequeño, (> N 0), entonces hay que: a] mover todos menos el mayor a la torre de apoyo o libre; b] mover el disco más grande a la torre de destino y c] mover todos los discos que se pusieron en la torre de apoyo a la torre destino". Los pasos (a) y(b) ya mencionados son llamadas recursivas. Cabe recordar que en el tema anterior hay una explicación sobre la recursividad.

Cuando se ejecuta el procedimiento, la computadora (o mejor dicho, el intérprete de Scheme que lo traduce a lenguaje de máquina y luego lo ejecuta en la computadora) asocia el nombre N con 3. También asocia fuente con 'A, que es un símbolo, etcétera (posteriormente se verá más de esto). Cuando se define un procedimiento, los nombres de los argumentos se llaman parámetros, aunque es usual llamarlos argumentos.

¡Y eso es todo!, el programa recursivo es prácticamente igual a la descripción recursiva del algoritmo del tema 2. Por supuesto, lleva un poco de tiempo acostumbrarse a la sintaxis del lenguaje y a los nombres de cada parte.

---