Torres de Hanói: encontre todos os movimentos

Você tem três hastes numeradas de 1 a 3. Alguns discos de tamanhos diferentes estão empilhados na primeira haste. Os discos estão ordenados por tamanho: o menor fica no topo e o maior, na base.

Crie uma função que mostre como transferir toda a pilha de n discos da primeira para a terceira haste, obedecendo às seguintes regras:

1. Cada movimento consiste em retirar o disco do topo de uma haste e colocá-lo em outra.
2. Um disco maior não pode ser colocado sobre um disco menor.

A função deve retornar uma lista de movimentos. Cada movimento é representado por uma tupla de dois números: o número da haste de onde retirar o disco e o número da haste onde colocá-lo.

Exemplos

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)]

Observações

• A função deve retornar uma lista vazia se n == 0
• A melhor maneira de resolver este problema é usar recursão.