Torre da Recursão
Torre de Hanói em 3D: resolva com 3, 4 e 5 discos, ensine ao robô a regra recursiva e veja ele resolver 8 discos, com a pilha de chamadas e o contador de movimentos.
Como usar
O desafio: leve todos os discos do pino A para o pino C. Só pode mover um disco por vez, sempre o de cima, e nunca colocar um disco maior em cima de um menor.
Você joga: clique num pino para pegar o disco de cima e depois no pino de destino (ou use os botões A, B e C, ou as teclas 1, 2 e 3). Robô resolve: primeiro ensine ao robô a regra, colocando os três passos na ordem certa. Depois escolha quantos discos ele vai mover e acompanhe a pilha de chamadas: cada linha é uma vez em que a regra chamou a si mesma.
Arraste o fundo da cena para girar; use a roda do mouse ou dois dedos para aproximar. Pelo teclado: Tab até a cena, setas giram e as teclas + e − aproximam. Todos os comandos também estão nos botões. Em computador mais lento, ligue o “Modo leve” embaixo da cena.
Discos
0 movimentos
1. Ensine a regra ao robô
Para mover n discos da origem para o destino, usando o pino que sobra como apoio:
E quando n = 1? É só mover o disco. Esse é o caso base, que faz a regra parar.
2. Quantos discos?
0 movimentos · 0 chamadas
Pilha de chamadas (a de baixo é a que está trabalhando agora):
Quantos movimentos?
Desafios
- Resolva com 3 discos usando só 7 movimentos.
- Resolva com 4 discos no número mínimo de movimentos.
- Ensine ao robô a regra recursiva, com os três passos na ordem certa.
- Veja o robô resolver 8 discos e descubra quantos movimentos seriam necessários com 10.
Para o professor
O que está por trás: a Torre de Hanói é o exemplo clássico de recursão, quando a solução de um problema usa a solução do mesmo problema, só que menor. Para mover n discos de A para C, basta mover n − 1 discos de A para B (o mesmo problema, com um disco a menos), mover o maior disco de A para C e, por fim, mover os n − 1 discos de B para C. A regra se chama a si mesma até chegar ao caso base (um disco só), que é resolvido direto e faz a recursão parar. A pilha de chamadas mostra isso acontecendo: cada chamada espera as chamadas de dentro terminarem, como as bonecas russas do plano de aula.
O número mínimo de movimentos é 2ⁿ − 1 (1, 3, 7, 15, 31...): cada disco a mais dobra o trabalho e soma 1. Com 64 discos, como na lenda dos monges, seriam mais de 18 quintilhões de movimentos, cerca de 585 bilhões de anos a um movimento por segundo. É um bom gancho para falar de crescimento exponencial e de algoritmos que ficam lentos demais.
Metodologia sugerida: aprendizagem por descoberta, em duplas. Primeiro as duplas resolvem com 3 e 4 discos e anotam quantos movimentos usaram. Depois tentam descrever com palavras como resolveram 4 discos “usando” a solução de 3. Só então abrem o modo Robô resolve e ensinam a regra.
- Para resolver 4 discos, quantas vezes vocês resolveram, sem perceber, a torre de 3?
- Por que a regra precisa de um caso base? O que aconteceria sem ele?
- Olhando a tabela, como achar o número de movimentos de 9 discos a partir do de 8? E com uma fórmula direta?
- Escrevam a regra em Python ou no Scratch (blocos personalizados podem chamar a si mesmos) e testem com 3 discos.
def torre(n, origem, destino, apoio):
if n == 1:
print("mova de", origem, "para", destino)
return
torre(n - 1, origem, apoio, destino)
print("mova de", origem, "para", destino)
torre(n - 1, apoio, destino, origem)
torre(3, "A", "C", "B")
Habilidade: EF08CO01 (construir soluções usando a técnica de recursão e automatizá-las com uma linguagem de programação); a tabela de movimentos conversa com sequências recursivas em Matemática. Combina com o plano de aula “Listas, recursão e algoritmos de ordenação”. Material concreto equivalente: três lápis em pé numa massinha e discos de papelão de tamanhos diferentes, ou moedas de valores diferentes empilhadas.