Este é um problema matemático  clássico  cuja  solução  envolve o
a aplicação do conceito de recursividade.  A "lenda"  que acompanha  esse
problema  conta  que em Benares,  durante  o reinado do  Imperador Fo Hi,
havia um templo com uma cúpula que  marcava o centro do  mundo (seja lá o
que  significa  "centro do mundo"). Dentro  dessa cúpula,  monges  moviam
grandes discos de ouro entre três grandes agulhas de diamante. Deus havia
colocado  64  discos de ouro  de  diâmetros diferentes na primeira agulha
durante a criação do universo e  disse que, quando os monges completassem
sua tarefa,  o universo chegaria ao fim. Essa tarefa  consistia em  mover
todos os discos dessa  primeira agulha para qualquer outra, sendo que:

        * somente um disco poderia ser movido por vez;
        * um disco não poderia ficar sobre um disco de diâmetro menor;
        * todos os discos com exceção  ao que está sendo movido  precisam
permanecer em uma das agulhas.

        Considerando  que  cada  movimento  poderia  ser realizado em  um
segundo e que não haveriam  movimentos  equivocados,  seriam  necessários
585,000,000,000 anos  para  que a  tarefa  fosse  completada.  Ainda  não
consegui  escrever  um  programa  capaz  de  mover  64 discos.  Se alguém
conseguir escrever um programa capaz de realizar esse cálculo,  por favor
me conte. Mas o número de vezes necessárias para realizar essa  tarefa  é
2^N -1 onde N é o  número de discos.  Por exemplo,  para 64  discos,  são
necessários 18,000,000,000,000,000,000 movimentos. Mesmo que  essa  lenda
fosse verdadeira, demoraria ainda um pouquinho para que o mundo acabasse.

        O algoritmo para mover os discos nas Torres de Hanói é:

	MoverDiscos (Agulhas: Horigem, Destino, Intermediária; Inteiro: NumDiscos)
	.	se NumDiscos = 0 retorna
	.	MoverDiscos (Horigem, Intermediária, Destino, NumDiscos -1)
	.	MoverUmDisco (Horigem, Destino)
	.	MoverDiscos (Intermediária, Destino, Horigem, NumDiscos -1)
	fim

        Esse  algoritmo  é  uma  função  recursiva  baseada  no  seguinte
princípio: para mover N discos de uma agulha A para uma agulha B, deve-se:

        * mover N -1 discos da agulha A para a agulha C;
        * mover o disco restante da agulha A para a agulha B;
        * mover os N -1 discos da agulha C para a agulha B.

        Mas para cada "mover N -1 discos..." deve-se  realizar  os  mesmos
três  passos,  até que  reste  apenas um disco na agulha horigem. A função 
"MoverUmDisco" é uma função abstrata que poderia ser  uma  manipulação  de
pilhas, ou uma função que mostrasse uma mensagem do tipo "mover  um  disco
da agulha A para a B".

        Toda rotina recursiva deve  ter  uma condição  de retorno. No caso
dessa, a condição de retorno é quando ocorre uma chamada pedindo que  zero
discos sejam movidos. É quando a cadeia de chamadas recursivas acaba.

        Para saber mais:

------> Exemplo em Pascal
------> Pilhas
------> Recursividade