┌──┴──┐ │ │
└──┬──┘ │ │
┌───┴───┐ │ │
└───┬───┘ │ │
┌────┴────┐ │ │
└────┬────┘ │ │
╔═════╧═════╗ ╔═════╧═════╗ ╔═════╧═════╗
A B C
┌──┴──┐ │ │
└──┬──┘ │ │
┌───┴───┐ │ │
└───┬───┘ │ │
╔═════╧═════╗ ╔═════╧═════╗ ╔═════╧═════╗
A B C
│ │ │
│ │ │
│ ┌──┴──┐ │
│ └──┬──┘ │
┌────┴────┐ ┌───┴───┐ │
└────┬────┘ └───┬───┘ │
╔═════╧═════╗ ╔═════╧═════╗ ╔═════╧═════╗
A B C
│ │ │
│ │ │
│ ┌──┴──┐ │
│ └──┬──┘ │
│ ┌───┴───┐ ┌────┴────┐
│ └───┬───┘ └────┬────┘
╔═════╧═════╗ ╔═════╧═════╗ ╔═════╧═════╗
A B C
│ │ ┌──┴──┐
│ │ └──┬──┘
│ │ ┌───┴───┐
│ │ └───┬───┘
│ │ ┌────┴────┐
│ │ └────┬────┘
╔═════╧═════╗ ╔═════╧═════╗ ╔═════╧═════╗
A B C
Então, assim, para resolver uma torre de 3 discos ele precisa saber resolver uma de 2 discos; para resolver a de 2 discos precisa saber resolver uma de 1 disco; ele sabe resolver de 1 disco. Isso funcionará para qualquer quantidade de discos e três torres.
Veja Determinar o n-ésimo termo de Fibonacci com recursividade para mais informações de como funciona a recursividade.