Resolver Las Torres de Hanoi recursivo

Hace algún tiempo se me planteó este típico ejercicio de programación en clase, el llamado Las Torres de Hanoi el cual conseguí resolver después de echarle mucho tiempo y hojas llenas de garabatos. Personalmente fue todo un reto y hoy os mostraré este ejercicio el cual si comprendes completamente, se te abrirá un mundo de posibilidades con la recursividad.

Como explicación muy básica, la recursividad se podría definir como la resolución de un problema de tamaño ( n ), el cual se puede dividir en partes más pequeñas ( <n ) del mismo problema, de los cuales si se conoce la solución.

El juego de Las Torres de Hanoi consiste en mover unos discos desde una varilla vertical a otra, empezando todos los discos en una varilla ordenados de más grande a más pequeño y habiendo 2 varillas más inicialmente vacías. Todo esto siguiendo las siguientes reglas:

1. Sólo puedes mover los discos de uno en uno.
2. Los discos tienen que estar ordenados en todo momento, los discos más grandes siempre debajo.
3. Sólo se puede mover los los discos de arriba de cada barilla.

Teniendo todo esto claro, se puede ver claramente que mover n discos de la varilla origen a la varilla destino, usando una varilla auxiliar, consiste en:

1. Mover todos los discos menos uno de origen a auxiliar.
2. Mover el último de origen a destino.
3. Mover todos los discos menos uno de auxiliar a origen.
4. Mover el último de auxiliar a destino.

Y este proceso se repite hasta que todos los discos estén en la varilla destino, puedes seguir este proceso en papel para ver como se resuelve el juego con 1, 2, 3, ..., n discos.

Teniendo todo este proceso pasamos a ver el ejercicio resuelto en Javascript, este lenguaje es estupendo para mostrar algoritmos ya que es un lenguaje muy sencillo y se puede seguir claramente sin tener grandes nociones del lenguaje.

var tower1 = [], tower2 = [], tower3 = [];
var n = 5; // Numero de discos

// Coloca en orden n discos en tower1
initTowers();
show(); // Estado inicial de las torres
hanoi(n, tower1, tower2, tower3);
show(); // Estado final de las torres

function hanoi(n, ori, aux, des) {
 // El caso base es mover 1 disco de ori a des
 if(n === 1) 
  mov(ori, des);
 else {
  // Se mueven n-1 discos de ori a aux
  hanoi(n - 1, ori, des, aux);
  mov(ori, des);
  // Se mueven n-1 discos de aux a des
  hanoi(n - 1, aux, ori, des);
 }
}
// Se mueve un disco de la torre ori a des
function mov(ori, des) { 
 des.push(ori.pop()); 
}
function initTowers() {
 for(var i = 0; i < n; i++) 
  tower1.push(n - i);
}
function show() {
 console.log(tower1);
 console.log(tower2);
 console.log(tower3);
 console.log();
}