Torres de Hanói: encuentra todos los movimientos

Tienes tres varillas numeradas del 1 al 3. En la primera varilla hay varios discos de distintos tamaños. Los discos están ordenados por tamaño: el más pequeño arriba y el más grande abajo.

Crea una función que muestre cómo transferir toda la pila de n discos desde la primera hasta la tercera varilla, respetando las siguientes reglas:

1. Cada movimiento consiste en tomar el disco superior de una varilla y colocarlo en otra.
2. No se puede colocar un disco más grande encima de uno más pequeño.

La función debe devolver una lista de movimientos. Cada movimiento se representa mediante una tupla de dos números: el número de la varilla de la que se toma el disco y el número de la varilla donde se coloca.

Ejemplos

hanoi(1) ➞ [(1, 3)]

hanoi(2) ➞ [(1, 2), (1, 3), (2, 3)]

hanoi(4) ➞ [(1, 2), (1, 3), (2, 3), (1, 2), (3, 1), (3, 2), (1, 2), (1, 3), (2, 3), (2, 1), (3, 1), (2, 3), (1, 2), (1, 3), (2, 3)]

Notas

• La función debe devolver una lista vacía si n == 0
• La mejor manera de resolver este problema es usar recursión.