Recursividade - Torre de Hanói

As seguintes definições foram adotadas nesta solução:

1) as torres foram nomeadas de 'A' (origem), 'B' (destino) e 'X' (apoio);
2) os discos empilhados na torre de origem são identificados numericamente mantendo a relação
   com os seus tamanhos, ficando sempre empilhados em ordem decrescente em uma determinada
   torre: do maior na base ao menor no topo da pilha;

Exemplo para 3 discos:

      |         |         |
      1         |         |
      2         |         |
    __3__     __|__     __|__

   Torre A   Torre X   Torre B

Conforme as regras desse problema, discos maiores não podem sobrepor discos menores em uma
determinada torre, sendo que a movimentação deles é livre entre as torres, desde de que
seja um disco por vez.

Para resolver o problema, a pilha de discos na torre de origem deve ser movida para a torre
de destino, usando uma torre extra para apoio à movimentação. 
 
Um algoritmo aplicando recursividade facilita a solução, pois devemos mover uma possível
pilha de discos que esteja sobre um disco maior em uma determinada torre antes de poder
mover esse disco maior para outra torre:


    função recursiva( disco, origem, destino, apoio ){

        se ( disco > 1 )
        {
            // mover antes para a torre de apoio uma possível pilha sobre um disco
            // que necessita ser movido para a torre de destino:
 
            recursiva( disco - 1, origem, apoio, destino );
        }

        // agora podemos mover o disco para a torre de destino após a pilha sobre ele
        // ter sido movida para a torre de apoio:

        escreva( "mover disco ", disco, " da torre ", origem, " para torre ", destino );

        se ( disco > 1 )
        {
            // mover a pilha de discos que está na torre de apoio para a de destino,
            // ficando esta sobre o disco que foi movido antes:

            recursiva( disco - 1, apoio, destino, origem );
        }
    }

    função principal(){
        recursiva( 3, 'A', 'B', 'X');
    }


Após a execução do algoritmo acima, a disposição dos discos nas torres será:

      |         |         |
      |         |         1
      |         |         2
    __|__     __|__     __3__

   Torre A   Torre X   Torre B 

A seguir temos o programa escrito na linguagem C:

#include <stdio.h>

int passo, qtd;

void function( int disco, char origem, char destino, char apoio ){
    if ( disco < 1 ) return;
    if ( disco > 1 ) function( disco - 1, origem, apoio, destino );
    printf( "\nPasso %d: mover disco %d de %c para %c", ++passo, disco, origem, destino );
    if ( disco > 1 ) function( disco - 1, apoio, destino, origem );
}

int main(void) {
    passo = 0;
    qtd = 3;
    function( qtd, 'A', 'B', 'X' );
    return 0;
}


Saída produzida pelo programa acima:

Passo 1: mover disco 1 de A para B
Passo 2: mover disco 2 de A para X
Passo 3: mover disco 1 de B para X
Passo 4: mover disco 3 de A para B
Passo 5: mover disco 1 de X para A
Passo 6: mover disco 2 de X para B
Passo 7: mover disco 1 de A para B


Para testar o programa acima, utilize a plataforma ideone.com:

https://ideone.com/qtypyY


Bom estudo e até a próxima.