Como funciona o teste da Torre de Hanoi na prática
A Torre de Hanoi é um exercício clássico de recursão que aparece em quase todo curso de programação básico. A ideia é simples: você tem três hastes e N discos empilhados, e precisa mover tudo de uma haste para outra, sem jamais colocar um disco maior sobre um menor. O teste cobra justamente isso. O que a maioria dos professores quer ver é sua capacidade de escrever a função recursiva correta e, mais importante, conseguir rastrear as chamadas mentalmente. Quando eu estava aprendendo C++, passei semanas travado nessa questão até entender que o segredo não é decorar o algoritmo, mas sim perceber o padrão de como os movimentos se alternam entre ímpar e par.
teste torre de hanoi
Para resolver, a lógica recursiva básica funciona assim: para mover n discos da haste de origem para a haste de destino usando uma auxiliar, você primeiro move n-1 discos para a auxiliar, depois move o disco n diretamente para o destino, e finalmente move os n-1 discos da auxiliar para o destino. Parece repetitivo de propósito, porque é exatamente isso. Um detalhe que poucos explicam bem: a quantidade total de movimentos necessários é 2^n - 1. Para 3 discos são 7 movimentos, para 5 discos são 31, e para 10 discos já são 1023. Isso é importante saber porque muitos algoritmos de validação em testes usam casos com n alto para testar eficiência, e soluções iterativas mal implementadas simplesmente não vão funcionar nesse cenário.
Me deparei uma vez com um sistema de avaliação que verificava não só a sequência correta dos movimentos, mas também se a solução usava recursão. Tinha um teste que injetava 15 discos e pedia para rastrear o tempo de execução. Minha solução recursiva ingênua levou cerca de 4 segundos, enquanto um colega otimizado com memoização chegou a 0,3 segundo. A diferença parecia pequena, mas o judge dava penalidade de performance se ultrapassasse um limiar fixo. Se você estiver escrevendo em Python, o código base fica mais ou menos assim:
def hanoi(n, origem, destino, auxiliar): if n == 1:
👉 Clique no botão abaixo para saber mais sobre o assunto!
print(f"Mover disco 1 de {origem} para {destino}") else:
hanoi(n-1, origem, auxiliar, destino) print(f"Mover disco {n} de {origem} para {destino}")
hanoi(n-1, auxiliar, destino, origem) O erro mais comum que eu vejo em provas e entrevistas é esquecer de considerar que, quando n é par, a haste destino e a auxiliar precisam ser trocadas na lógica de movimentação dos discos menores. Se você tratar todos os casos como se fossem ímpar, o teste vai falhar silenciosamente nos casos com 2, 4, 6 discos. Não custa implementar uma verificação adicional antes de rodar o algoritmo principal.
Outro problema frequente: validar a solução sem considerar o estado intermediário. Alguns judges exigem que você mostre cada estado das hastes após cada movimento, não apenas a sequência final. Nesse caso, você precisa manter vetores ou pilhas representando cada haste e atualizá-los a cada iteração, o que aumenta a complexidade mas é essencial para passar nos testes automatizados. Se você quer testar sua implementação, alguns sites úteis incluem a plataforma Beecrowd (antigo URI Online Judge), que tem um problema chamado "Torre de Hanoi" com validação passo a passo. Também recomendo escrever um visualizador simples em uma linguagem que você domine para acompanhar os movimentos em tempo real, porque ver funcionando ajuda muito mais do que tentar debugar no papel.
A desvantagem de focar apenas na versão recursiva é que ela consome memória de stack proporcional a n, o que em linguagens como Java ou C++ pode dar stack overflow para n acima de 1000. Se o teste exigir tamanhos grandes, prefira uma abordagem iterativa baseada no teorema de Gray code, que gera a sequência de movimentos de forma determinística sem recursão. Não existe solução perfeita para todos os cenários de teste. O mais sensato é dominar ambas as abordagens, saber quando usar cada uma, e garantir que seu código lide corretamente com casos de borda como n igual a zero ou entradas negativas, porque esses são exatamente os testes que a maioria dos alunos deixa passar e que mais costuma derrubar a nota.
