javascript - Función de hanoi de Crockford(de "The Good Parts")
recursion towers-of-hanoi (2)
La confusión surge porque la representación de texto del resultado no es la mejor manera de entender la recursión. La cantidad de discos no "sube", sino que es hanoi(1) que continúa ejecutándose una vez que hanoi(0) está listo.
He creado un ejemplo modificado en JSBin que imprime el resultado de una manera (algo) más bonita con espacios. Solo los "movimientos" realmente hacen algo, el resto de las líneas son solo llamadas recursivas para resolver sub-problemas más pequeños con el fin de abordar todo el problema más adelante.
Es posible que también desee echarle un vistazo a este applet de Java que muestra gráficamente cómo funciona el algoritmo; esto podría ser más fácil de entender.
Esta pregunta ya tiene una respuesta aquí:
En este momento estoy leyendo el libro de Douglas Crockford, y las torres de la función de hanoi están un poco sobre mi cabeza. Incluso con el registro de cosas en la consola, no pude entender realmente lo que está sucediendo. Aquí está la función con mis adiciones:
var hanoi = function (disc, src, aux, dst) {
console.log(disc);
console.log(src, dst);
if (disc > 0) {
hanoi(disc - 1, src, dst, aux);
console.log(''Move disc '' + disc + '' from '' + src + '' to '' + dst);
hanoi(disc - 1, aux, src, dst);
}
}
hanoi(3, ''Src'', ''Aux'', ''Dst'');
Esto resulta en lo siguiente:
3
Src Dst
2
Src Aux
1
Src Dst
0
Src Aux
Mueve el disco 1 de Src a Dst
0
Aux Dst
Mueva el disco 2 de Src a Aux
1
Dst Aux
0
Dst Src
Mueva el disco 1 de Dst a Aux
0
Src Aux
Mueve el disco 3 de Src a Dst
2
Aux Dst
1
Aux Src
0
Aux Dst
Mueva el disco 1 de Aux a Src
0
Dst Src
Mueva el disco 2 de Aux a Dst
1
Src Dst
0
Src Aux
Mueve el disco 1 de Src a Dst
0
Aux Dst
Y estoy perdido en un punto temprano. En la línea 6 de los resultados, ¿cómo puede volverse de Src Aux a Src Dst?
¿Y cómo puede la cantidad de discos volver a subir una vez que ha llegado a 0, cuando la función solo se está llamando usando "disco - 1"?
Towers of Hanoi es un excelente ejemplo de cómo la recursividad puede simplificar un problema determinado. La idea es la siguiente: tiene que mover N discos de una pila fuente a una pila de destino, un disco a la vez y nunca puede colocar un disco más grande en uno más pequeño. Puedes usar una pila auxiliar. Digamos que N = 10. No tienes idea de cómo resolverlo. Pero puedes simplificar el problema (esperas):
move 9 disks to the auxiliary stack,
move the remaining (and largest!) disk to the destination stack, and
move the 9 disks from the auxiliary stack to the destination stack
De nuevo, no tienes idea de cómo mover una pila de 9 discos, pero tampoco hay problema:
move 8 disks from the auxiliary stack to the source stack,
move the remaining disk to the destination stack (there are 2 disks now), and
move the 8 disks from the source stack to the destination stack
Repite esto hasta que la pila que tienes que mover tenga solo 1 disco grande.
Acerca del número de discos que vuelven a subir: llama a la función recursivamente para discos N-1, que en la función se asignan a N. Este N solo existe hasta que la función finaliza y vuelve al nivel anterior. Luego obtienes el antiguo valor de N nuevamente.