📚 Capítulo do curso: 09 — Recursividade, Pilha de Execução e Tail Recursion da Especialização em Sistemas com C. Leia o capítulo antes de começar.

🗼 Miniprojeto C 09 — Torres de Hanói Recursivas

Um solucionador recursivo do clássico quebra-cabeça das Torres de Hanói, com contagem de movimentos.

🔒 Regra de Ouro: até o Capítulo 09, você ganha recursão — uma função que chama a si mesma, sempre com um caso base explícito que interrompe a cadeia de chamadas antes que ela vire infinita. Este miniprojeto tem exatamente uma função recursiva, hanoi, que resolve o problema dividindo-o em subproblemas menores até chegar ao caso base.

🎯 Objetivos

• Escrever uma função recursiva com caso base correto (if (n == 0) return;), evitando recursão infinita.
• Entender como um problema grande (mover n discos) se decompõe em dois subproblemas menores (mover n-1 discos) mais um movimento único.
• Usar static dentro de uma função recursiva para acumular um contador que sobrevive a todas as chamadas recursivas, não só à chamada atual.
• Validar a entrada do usuário antes de iniciar uma recursão potencialmente cara.

📋 O problema

Construa um solucionador das Torres de Hanói (main.c) com uma função recursiva:

void hanoi(int n, char origem, char auxiliar, char destino);

Ela deve imprimir, um por um, cada movimento necessário para transferir n discos da torre origem para a torre destino, usando auxiliar como torre auxiliar. O main lê n via scanf, com um limite de segurança: valores de n menores que 1 ou maiores que 15 devem ser recusados com uma mensagem de erro em stderr, sem executar a recursão. Ao final, o programa deve imprimir o número total de movimentos realizados, para conferência com a fórmula matemática conhecida 2^n - 1.

graph TD
    A["hanoi(3, A, B, C)"] --> B["hanoi(2, A, C, B)"]
    A --> M3["move disco 3: A -> C"]
    A --> D["hanoi(2, B, A, C)"]
    B --> E["hanoi(1, A, B, C)"]
    B --> M2["move disco 2: A -> B"]
    B --> F["hanoi(1, C, A, B)"]
    E --> BC1["caso base n=0 (x2)"]
    E --> M1a["move disco 1: A -> C"]
    F --> M1b["move disco 1: C -> B"]

    style A fill:#0284c7,stroke:#38bdf8,color:#ffffff
    style BC1 fill:#dc2626,stroke:#f87171,color:#ffffff

🧰 Ambiente

O mesmo do Miniprojeto 01: gcc 8 ou mais novo. No Windows, rode chcp 65001 se os emojis aparecerem quebrados.

Passo 1 — Compilar o esqueleto

🎯 Objetivo: partir de um código que compila e roda, antes de escrever qualquer linha.

⌨️ Faça: crie a pasta c_mini_09, salve o código abaixo como main.c e rode:

gcc -Wall -Wextra -Wpedantic -std=c17 main.c -o app
./app          # Linux/macOS
.\app.exe      # Windows (PowerShell)

📄 src/esqueleto.c

/*
 * Miniprojeto 09: Solucionador Recursivo de Torres de Hanoi
 * Regra: recursao com caso base explicito (Capitulo 09).
 */
#include <stdio.h>
#include <stdlib.h>

// TODO 1: declare o prototipo da funcao recursiva:
// void hanoi(int n, char origem, char auxiliar, char destino);

int main(void) {
    int discos = 0;

    printf("====================================================\n");
    printf(" 🗼 SOLUCIONADOR RECURSIVO DE TORRES DE HANOI\n");
    printf("====================================================\n");
    printf("Quantidade de discos (1 a 15): ");
    scanf("%d", &discos);

    // TODO 2: valide "discos" (deve ser >= 1 e <= 15). Se invalido,
    // imprima erro em stderr com fprintf e retorne EXIT_FAILURE.

    printf("\nMovimentos necessarios:\n");
    // TODO 3: chame hanoi(discos, 'A', 'B', 'C');

    // TODO 4: calcule 2^discos - 1 com um "for" (sem usar pow()) numa
    // variavel "long esperado" e imprima para comparar com o total
    // de movimentos impresso pela recursao

    return EXIT_SUCCESS;
}

// TODO 5: implemente void hanoi(int n, char origem, char auxiliar, char destino)
// com:
//   - caso base: if (n == 0) return;
//   - "static int movimentos = 0;" para contar cada movimento impresso
//   - a chamada hanoi(n - 1, origem, destino, auxiliar);
//   - a impressao do movimento do disco "n" de origem para destino
//   - a chamada hanoi(n - 1, auxiliar, origem, destino);

✅ Checkpoint: zero avisos do gcc, e a saída é:

🖥️ Saída esperada:

====================================================
 🗼 SOLUCIONADOR RECURSIVO DE TORRES DE HANOI
====================================================
Quantidade de discos (1 a 15): 
Movimentos necessarios:

Ao rodar, digite 3 e Enter. A saída acima é a do teste automático, com o 3 enviado por redirecionamento, por isso ele não aparece depois da pergunta.

Passo 2 — Validar antes de recursar (TODO 2)

🎯 Objetivo: recusar entradas que fariam a recursão explodir: 2^30 movimentos levariam horas.

⌨️ Faça: depois do scanf, se discos < 1 || discos > 15, imprima um erro com fprintf(stderr, ...) e return EXIT_FAILURE;.

✅ Checkpoint: digitar 20 mostra o erro e echo $? (ou echo $LASTEXITCODE) dá 1. Digitar 3 continua chegando a Movimentos necessarios:.

Passo 3 — A função recursiva (TODO 1, 3 e 5)

🎯 Objetivo: resolver o problema de n discos com dois subproblemas de n - 1 e um movimento.

⌨️ Faça: declare o protótipo de hanoi antes do main e implemente-a depois dele:

1. static int movimentos = 0;
2. Caso base: if (n == 0) return;
3. hanoi(n - 1, origem, destino, auxiliar); tira os n - 1 de cima do caminho;
4. incrementa movimentos e imprime Movimento %d: mova o disco %d de %c para %c;
5. hanoi(n - 1, auxiliar, origem, destino); põe os n - 1 de volta em cima.

No main, chame hanoi(discos, 'A', 'B', 'C');.

✅ Checkpoint: com 3 discos aparecem 7 movimentos. O primeiro é disco 1 de A para C, e o do meio (o 4º) move o disco 3, o maior, de A para C.

🧯 Se der errado:

• O programa trava ou termina com Segmentation fault / código -1073741571 (Windows): faltou o caso base, ou ele vem depois das chamadas recursivas. A pilha de execução estourou.
• Os movimentos não terminam em C: a ordem dos parâmetros nas duas chamadas recursivas está trocada. Compare com o diagrama.

Passo 4 — Conferir com a fórmula (TODO 4)

🎯 Objetivo: validar a recursão com um resultado matemático independente.

⌨️ Faça: calcule 2^discos - 1 num long esperado, com um for que dobra o valor discos vezes, e imprima Formula 2^n - 1 para n=%d discos = %ld movimentos.

✅ Checkpoint: o número da fórmula é igual ao último Movimento N.

Passo final — Conferir com o gabarito

🎯 Objetivo: validar a saída completa e o código de retorno.

⌨️ Faça: crie entrada.txt na pasta do projeto, com o conteúdo abaixo, e rode o programa com a entrada redirecionada:

📄 tests/main.entrada.txt

3

./app < entrada.txt                    # Linux/macOS
Get-Content entrada.txt | .\app.exe    # Windows (PowerShell)

✅ Checkpoint: com a entrada redirecionada o terminal não ecoa o que seria digitado, então as respostas não aparecem depois das perguntas. A saída tem que bater com esta, e o código de retorno é 0 (echo $? ou echo $LASTEXITCODE):

🖥️ Saída esperada:

====================================================
 🗼 SOLUCIONADOR RECURSIVO DE TORRES DE HANOI
====================================================
Quantidade de discos (1 a 15): 
Movimentos necessarios:
  Movimento 1: mova o disco 1 de A para C
  Movimento 2: mova o disco 2 de A para B
  Movimento 3: mova o disco 1 de C para B
  Movimento 4: mova o disco 3 de A para C
  Movimento 5: mova o disco 1 de B para A
  Movimento 6: mova o disco 2 de B para C
  Movimento 7: mova o disco 1 de A para C

Formula 2^n - 1 para n=3 discos = 7 movimentos

Só abra o gabarito depois de chegar até aqui:

/*
 * Miniprojeto 09: Solucionador Recursivo de Torres de Hanoi
 * Especializacao em Engenharia de Sistemas em C
 * Regra: recursao com caso base explicito (Capitulo 09).
 */
#include <stdio.h>
#include <stdlib.h>

void hanoi(int n, char origem, char auxiliar, char destino);

int main(void) {
    int discos = 0;

    printf("====================================================\n");
    printf(" 🗼 SOLUCIONADOR RECURSIVO DE TORRES DE HANOI\n");
    printf("====================================================\n");
    printf("Quantidade de discos (1 a 15): ");
    scanf("%d", &discos);

    if (discos < 1 || discos > 15) {
        fprintf(stderr, "ERRO: numero de discos invalido. Use um valor entre 1 e 15.\n");
        return EXIT_FAILURE;
    }

    printf("\nMovimentos necessarios:\n");
    hanoi(discos, 'A', 'B', 'C');

    long esperado = 1L;
    for (int i = 0; i < discos; i++) {
        esperado = esperado * 2;
    }
    esperado = esperado - 1;

    printf("\nFormula 2^n - 1 para n=%d discos = %ld movimentos\n", discos, esperado);

    return EXIT_SUCCESS;
}

void hanoi(int n, char origem, char auxiliar, char destino) {
    static int movimentos = 0;

    if (n == 0) {
        return; // caso base: nao ha disco algum para mover
    }

    hanoi(n - 1, origem, destino, auxiliar);

    movimentos = movimentos + 1;
    printf("  Movimento %d: mova o disco %d de %c para %c\n", movimentos, n, origem, destino);

    hanoi(n - 1, auxiliar, origem, destino);
}

Por que isso importa: o caso base if (n == 0) return; é o que impede a recursão de continuar para sempre — cada chamada recursiva trabalha com n - 1, então, mais cedo ou mais tarde, n chega a 0 e a função simplesmente retorna sem fazer mais chamadas. O contador static int movimentos é declarado dentro de hanoi, mas como é static, ele não é recriado a cada chamada recursiva — existe uma única cópia dessa variável, compartilhada por todas as ativações da função na pilha de recursão, o que permite contar corretamente o total de movimentos em todas elas.

🏆 Desafio

Modifique o programa para também imprimir, antes de cada movimento, a profundidade atual da recursão (quantos discos ainda faltam mover na chamada corrente) — isso te dá uma visão informal de como a pilha de chamadas (call stack) cresce e depois diminui. Se quiser ir além, pesquise sobre memoização e pense por que ela não ajuda em nada nas Torres de Hanói (dica: compare com o Fibonacci recursivo — aqui não há subproblemas repetidos para reaproveitar).

✅ Checkpoint: com 4 discos são 15 movimentos, e o disco 4 se move uma única vez, no 8º movimento. Com 10 discos são 1023.

🧭 Navegação

📋 Projetos do curso de C | 📚 Teoria do Capítulo 09 | 🗂️ Hub de projetos