Semana 06 — Recursão¶

Nesta semana

Unidade 2 · Seg 14/09 · Qua 16/09 · Sex 18/09

Na Semana 04 aprendemos a criar funções — blocos com nome que resolvem uma parte do problema. Agora vamos dar a essas funções um poder que, à primeira vista, parece um truque de mágica: uma função pode chamar a si mesma. Isso se chama recursão, e é uma das ideias mais elegantes (e mais confusas, no começo) de toda a programação. A boa notícia: assim que a "ficha cai", muitos problemas passam a parecer surpreendentemente simples.

Vamos entender por que a recursão funciona (a resposta está na pilha de chamadas, que já mencionamos na Semana 04), quais são os dois ingredientes obrigatórios de toda recursão, e quando ela vale a pena frente a um bom e velho laço. Prepare papel e caneta: nesta semana, desenhar o que o programa faz é meio caminho andado.

🎯 Objetivos de aprendizagem¶

Ao final desta semana, você deverá ser capaz de:

explicar, com suas palavras, o que é uma função recursiva e dar exemplos do cotidiano e da matemática;
identificar e escrever os dois elementos indispensáveis de toda recursão: o caso base e o caso recursivo;
simular no papel a execução de uma função recursiva, acompanhando a pilha de chamadas empilhar e desempilhar;
escrever funções recursivas corretas para problemas clássicos (fatorial, soma, potência, Fibonacci, MDC);
comparar recursão e iteração (laços), reconhecendo os prós e contras de cada abordagem;
reconhecer as causas de uma recursão infinita e do temido estouro de pilha (stack overflow);
entender por que o Fibonacci recursivo ingênuo é exponencialmente lento.

📖 Segunda — Estudo do conteúdo¶

1. O que é recursão?¶

Recursão acontece quando uma função chama a si mesma para resolver uma versão menor do mesmo problema. Parece estranho — como algo pode ser definido em termos de si próprio sem virar um raciocínio circular vicioso? A chave está em uma palavra: menor. Cada vez que a função se chama, o problema encolhe um pouquinho, até ficar tão simples que a resposta é imediata.

Você convive com recursão fora da computação sem perceber:

Bonecas russas (matrioscas): abrir uma boneca revela outra boneca menor dentro, e assim por diante — até chegar à menor de todas, que não abre. "Abrir a boneca" é definido em termos de "abrir a boneca de dentro".
Dois espelhos frente a frente: cada espelho reflete o outro, que reflete o primeiro, que reflete o outro… gerando uma sequência de reflexos cada vez menores.
A definição de fatorial: na matemática, o fatorial já é definido recursivamente:

$$ n! = \begin{cases} 1 & \text{se } n = 0 \ n \times (n-1)! & \text{se } n > 0 \end{cases} $$

Repare que 5! é definido usando 4!, que usa 3!, que usa 2!… até 0!, que vale 1 sem depender de mais ninguém. É exatamente esse "ponto de parada" que impede o raciocínio de girar para sempre.

Curiosidade 💡 — recursão está em toda parte na definição das coisas

Muitas estruturas são naturalmente recursivas: uma pasta de arquivos contém arquivos e outras pastas (que contêm arquivos e outras pastas…); uma frase pode conter outra frase ("Ele disse que ela disse que…"); uma árvore genealógica se ramifica em ancestrais que também têm ancestrais. Quando você perceber esse padrão de "algo que contém uma versão menor de si mesmo", a recursão costuma ser a ferramenta certa.

2. Os dois elementos indispensáveis¶

Toda função recursiva corretamente escrita tem dois ingredientes. Se faltar qualquer um deles, a recursão não funciona.

Caso base (condição de parada): o caso mais simples, cuja resposta é conhecida diretamente, sem precisar de mais nenhuma chamada. É o que encerra a recursão. No fatorial, o caso base é 0! = 1.
Caso recursivo: o passo em que a função chama a si mesma para um problema menor, caminhando em direção ao caso base. No fatorial, é n! = n * (n-1)!.

Em pseudocódigo, o esqueleto de toda função recursiva é sempre este:

funcao resolve(problema):
    se problema é o caso mais simples:      <- CASO BASE
        devolve a resposta direta
    senao:                                  <- CASO RECURSIVO
        devolve algo combinado com resolve(problema menor)

A regra de ouro da recursão

O caso recursivo precisa se aproximar do caso base a cada chamada. Se você chama fatorial(n) de dentro de fatorial(n) (sem diminuir o n), ou se o caso base nunca é alcançado, a função se chama para sempre — e o programa quebra (veja a seção 6). Sempre pergunte: "a cada chamada, o problema fica realmente menor? E ele consegue chegar ao caso base?"

Vejamos o fatorial já em C, com os dois elementos claramente marcados:

long fatorial(int n) {
    if (n == 0) {          // CASO BASE: 0! = 1
        return 1;
    }
    return n * fatorial(n - 1);   // CASO RECURSIVO: n! = n * (n-1)!
}

Simples assim: três linhas substituem um laço. Mas o que acontece por baixo quando chamamos fatorial(4)? É o que a próxima seção revela.

3. Como a pilha de chamadas executa a recursão¶

Na Semana 04 vimos, na curiosidade sobre a pilha de chamadas (call stack), que cada chamada de função cria um "quadro" (stack frame) na memória, contendo os parâmetros e as variáveis locais daquela chamada. Quando a função retorna, o quadro é desempilhado. É esse mecanismo que torna a recursão possível: cada chamada de fatorial tem o seu próprio n, independente das outras.

Vamos acompanhar fatorial(4) passo a passo. Primeiro, as chamadas vão se empilhando (fase de "descida"), porque cada uma precisa do resultado da próxima antes de poder calcular o seu:

fatorial(4) = 4 * fatorial(3)      <- precisa de fatorial(3)... espera
  fatorial(3) = 3 * fatorial(2)    <- precisa de fatorial(2)... espera
    fatorial(2) = 2 * fatorial(1)  <- precisa de fatorial(1)... espera
      fatorial(1) = 1 * fatorial(0)<- precisa de fatorial(0)... espera
        fatorial(0) = 1            <- CASO BASE! resposta direta, sem esperar ninguem

Chegamos ao caso base. Agora a pilha desempilha (fase de "subida"), e cada chamada finalmente calcula o seu return, de baixo para cima:

        fatorial(0) devolve 1
      fatorial(1) devolve 1 * 1  = 1
    fatorial(2) devolve 2 * 1    = 2
  fatorial(3) devolve 3 * 2      = 6
fatorial(4) devolve 4 * 6        = 24

Resultado final: fatorial(4) = 24. Note o padrão em "V": primeiro desce empilhando chamadas até o caso base, depois sobe desempilhando e multiplicando.

Visualmente, a pilha em seu momento mais "cheio" (logo antes do caso base retornar):

flowchart TB
    subgraph pilha["Pilha de chamadas (topo embaixo)"]
    F4["fatorial(4): n=4, aguarda fatorial(3)"]
    F3["fatorial(3): n=3, aguarda fatorial(2)"]
    F2["fatorial(2): n=2, aguarda fatorial(1)"]
    F1["fatorial(1): n=1, aguarda fatorial(0)"]
    F0["fatorial(0): n=0, retorna 1 (caso base)"]
    end
    F4 --> F3 --> F2 --> F1 --> F0

O melhor jeito de entender recursão: desenhe a pilha

Quando uma recursão parecer confusa, pare e desenhe as chamadas empilhando e depois os return subindo, exatamente como fizemos acima. Escolha um valor pequeno (fatorial(3), fib(4)) e siga cada passo com papel e caneta. Depois de fazer isso duas ou três vezes, a recursão deixa de ser "mágica" e vira mecânica.

4. Exemplos clássicos¶

Vamos ver quatro clássicos, cada um com código completo e correto. Em todos, encontre mentalmente o caso base e o caso recursivo.

4.1 Fatorial¶

Já vimos a função; aqui está o programa completo:

fatorial.c

#include <stdio.h>

long fatorial(int n) {
    if (n == 0) {              // caso base
        return 1;
    }
    return n * fatorial(n - 1);   // caso recursivo
}

int main(void) {
    int n;
    printf("Digite um inteiro nao-negativo: ");
    scanf("%d", &n);
    printf("%d! = %ld\n", n, fatorial(n));
    return 0;
}

4.2 Soma de 1 até n¶

Queremos 1 + 2 + 3 + ... + n. A ideia recursiva: a soma até n é n mais a soma até n-1. O caso base é a soma até 0, que é 0.

soma.c

#include <stdio.h>

int soma_ate(int n) {
    if (n == 0) {             // caso base: soma de nada e' 0
        return 0;
    }
    return n + soma_ate(n - 1);   // caso recursivo
}

int main(void) {
    printf("%d\n", soma_ate(5));  // 5 + 4 + 3 + 2 + 1 + 0 = 15
    return 0;
}

4.3 Potência (base elevado a exp)¶

Queremos calcular base^exp (com exp inteiro não-negativo). A ideia: base^exp é base vezes base^(exp-1). O caso base é base^0, que vale 1 (qualquer número elevado a zero é 1).

potencia.c

#include <stdio.h>

long potencia(int base, int exp) {
    if (exp == 0) {                 // caso base: base^0 = 1
        return 1;
    }
    return base * potencia(base, exp - 1);   // caso recursivo
}

int main(void) {
    printf("%ld\n", potencia(2, 10));  // 2^10 = 1024
    printf("%ld\n", potencia(5, 3));   // 5^3  = 125
    return 0;
}

4.4 Fibonacci¶

A sequência de Fibonacci é 0, 1, 1, 2, 3, 5, 8, 13, ...: cada termo é a soma dos dois anteriores. Sua definição já é naturalmente recursiva, com dois casos base:

$$ fib(n) = \begin{cases} 0 & \text{se } n = 0 \ 1 & \text{se } n = 1 \ fib(n-1) + fib(n-2) & \text{se } n \ge 2 \end{cases} $$

fibonacci.c

#include <stdio.h>

long fib(int n) {
    if (n == 0) return 0;          // caso base 1
    if (n == 1) return 1;          // caso base 2
    return fib(n - 1) + fib(n - 2);   // caso recursivo (DUAS chamadas!)
}

int main(void) {
    for (int i = 0; i < 10; i++) {
        printf("%ld ", fib(i));    // 0 1 1 2 3 5 8 13 21 34
    }
    printf("\n");
    return 0;
}

Repare em algo diferente: no caso recursivo, a função se chama duas vezes. Isso tem um preço alto, como veremos na seção 7.

5. Recursão × iteração (laços)¶

Existe um teorema clássico da computação: toda solução recursiva pode ser reescrita com um laço, e vice-versa. As duas abordagens são igualmente "poderosas"; a escolha é uma questão de clareza e eficiência.

Compare o fatorial nas duas versões:

// Versao RECURSIVA
long fat_rec(int n) {
    if (n == 0) return 1;
    return n * fat_rec(n - 1);
}

// Versao ITERATIVA (com laco)
long fat_iter(int n) {
    long resultado = 1;
    for (int i = 2; i <= n; i++) {
        resultado *= i;
    }
    return resultado;
}

Qual usar? Depende. A tabela resume os prós e contras:

Aspecto	Recursão	Iteração (laço)
Legibilidade	Muito elegante em problemas naturalmente recursivos (árvores, Hanói, fractais).	Mais direta em contas simples e repetições.
Memória	Gasta memória da pilha: um quadro por chamada. Recursão profunda pode estourar a pilha.	Usa memória constante (as mesmas variáveis do laço).
Velocidade	Às vezes mais lenta: há o custo de chamar a função (empilhar/desempilhar).	Em geral um pouco mais rápida.
Risco	Recursão infinita → stack overflow (seção 6).	Laço infinito → programa "trava", mas sem estourar pilha.

Regra prática para escolher

Se o problema é naturalmente recursivo e a recursão deixa o código muito mais claro (percorrer estruturas ramificadas, Torres de Hanói, "dividir e conquistar"), prefira a recursão. Se é uma repetição simples que pode ficar muito profunda (somar um milhão de números), prefira o laço — ele não corre risco de estourar a pilha. Nas duas primeiras unidades, use a que você entende melhor; o importante agora é compreender os dois mundos.

6. Recursão infinita e o estouro de pilha¶

O erro número um de quem começa com recursão é esquecer o caso base — ou escrever um caso base que nunca é atingido. Sem um ponto de parada válido, a função se chama indefinidamente:

// ERRADO: nao ha caso base!
long fatorial_quebrado(int n) {
    return n * fatorial_quebrado(n - 1);   // chama, chama, chama... para sempre
}

// ERRADO: caso base INATINGIVEL
long fatorial_quebrado2(int n) {
    if (n == 0) return 1;
    return n * fatorial_quebrado2(n + 1);  // n CRESCE: nunca chega a 0!
}

O primeiro nunca para porque não há caso base. O segundo tem caso base (n == 0), mas o caso recursivo afasta n do zero (n + 1) em vez de aproximá-lo — o caso base jamais é alcançado.

Em ambos, cada chamada empilha um novo quadro na pilha, que tem tamanho limitado. Quando a pilha enche, o programa é abortado com um erro de estouro de pilha (stack overflow) — no Linux, tipicamente um Segmentation fault.

Os três pecados capitais da recursão

Não ter caso base. A função nunca sabe quando parar.
Caso base inatingível. O caso recursivo não caminha em direção a ele (esqueceu de diminuir n, ou diminuiu na direção errada).
Ordem trocada. Colocar a chamada recursiva antes do teste do caso base, de modo que o teste nunca chega a rodar.

O sintoma dos três é o mesmo: o programa consome a pilha até estourar. Ao ver um Segmentation fault numa função recursiva, desconfie do caso base primeiro.

Curiosidade 💡 — a origem do termo stack overflow

"Stack" é a pilha de chamadas; "overflow" é transbordamento. O nome vem literalmente da ideia de uma pilha de pratos que você não para de empilhar: uma hora ela transborda e desaba. O sistema operacional reserva um espaço fixo para a pilha de cada programa (na casa dos poucos megabytes); recursão descontrolada o esgota. Curiosamente, o site de perguntas e respostas mais famoso entre programadores, o Stack Overflow, foi batizado exatamente com o nome desse erro clássico.

7. Recursão múltipla e o custo do Fibonacci ingênuo¶

Quando o caso recursivo faz mais de uma chamada a si mesmo, temos recursão múltipla. O Fibonacci da seção 4.4 é o exemplo canônico: fib(n) chama fib(n-1) e fib(n-2). Isso parece inofensivo, mas esconde um desperdício gigantesco.

Desenhe a árvore de chamadas de fib(5):

flowchart TB
    A["fib(5)"] --> B["fib(4)"]
    A --> C["fib(3)"]
    B --> D["fib(3)"]
    B --> E["fib(2)"]
    C --> F["fib(2)"]
    C --> G["fib(1)"]
    D --> H["fib(2)"]
    D --> I["fib(1)"]
    E --> J["fib(1)"]
    E --> K["fib(0)"]
    F --> L["fib(1)"]
    F --> M["fib(0)"]
    H --> N["fib(1)"]
    H --> O["fib(0)"]

Perceba o problema: fib(3) é calculado duas vezes, fib(2) três vezes, e assim por diante. A função recalcula do zero os mesmos valores repetidamente. À medida que n cresce, o número de chamadas quase dobra a cada incremento — o custo é exponencial (aproximadamente 2^n chamadas). fib(50) recursivo ingênuo faria bilhões de chamadas e demoraria uma eternidade, enquanto a versão com laço faz 50 passinhos e responde num piscar de olhos.

fib_iterativo.c

// Fibonacci ITERATIVO: linear, rapidissimo
long fib_iter(int n) {
    if (n < 2) return n;
    long anterior = 0, atual = 1;
    for (int i = 2; i <= n; i++) {
        long proximo = anterior + atual;
        anterior = atual;
        atual = proximo;
    }
    return atual;
}

Curiosidade 💡 — por que o Fibonacci ingênuo é exponencialmente lento

O número de chamadas para calcular fib(n) recursivamente cresce, ele próprio, quase como a sequência de Fibonacci — ou seja, de forma exponencial (na base do "número de ouro", ≈ 1,618). Traduzindo: cada +1 no n multiplica o trabalho por ~1,6. O culpado é o recálculo dos mesmos subproblemas. Existe uma técnica para curar isso, chamada memoização (guardar os resultados já calculados numa tabela para não repetir o trabalho) — você a estudará mais adiante, quando vir vetores e programação dinâmica. Por ora, guarde a lição: recursão múltipla que recalcula subproblemas pode ser desastrosamente lenta.

Curiosidade 💡 — recursão de cauda (tail recursion)

Diz-se que uma recursão é de cauda quando a chamada recursiva é a última coisa que a função faz — não há nenhuma operação pendente depois dela (nem uma multiplicação, nem uma soma esperando o retorno). Nesses casos, alguns compiladores conseguem otimizar a recursão, transformando-a internamente em um laço e evitando empilhar quadros (tail-call optimization). O fatorial da seção 4.1 não é de cauda, pois ainda falta multiplicar por n depois do retorno; já uma versão que carrega um "acumulador" como parâmetro pode ser. É um assunto avançado — cite-o apenas para saber que ele existe.

Curiosidade 💡 — as Torres de Hanói

As Torres de Hanói são o exemplo perfeito de problema naturalmente recursivo. Há três pinos e n discos de tamanhos diferentes, empilhados do maior (embaixo) ao menor (em cima) no pino de origem. O objetivo é mover toda a pilha para o pino de destino, movendo um disco por vez e nunca pondo um disco maior sobre um menor. A solução recursiva é lindíssima: para mover n discos da origem ao destino, (1) mova n-1 discos para o pino auxiliar, (2) mova o maior disco para o destino, (3) mova os n-1 discos do auxiliar para o destino.

void hanoi(int n, char origem, char destino, char auxiliar) {
    if (n == 1) {                              // caso base: 1 disco
        printf("Mover disco 1 de %c para %c\n", origem, destino);
        return;
    }
    hanoi(n - 1, origem, auxiliar, destino);   // passo 1
    printf("Mover disco %d de %c para %c\n", n, origem, destino);  // passo 2
    hanoi(n - 1, auxiliar, destino, origem);   // passo 3
}
// chamada: hanoi(3, 'A', 'C', 'B');

Resolver Hanói com laços é possível, mas muito mais difícil de escrever e entender — é aqui que a recursão realmente brilha.

8. Erros comuns desta semana (resumão)¶

Checklist de armadilhas

Esquecer o caso base — recursão infinita, estouro de pilha.
Caso base inatingível — o caso recursivo não caminha em direção a ele.
Testar o caso base depois de já ter feito a chamada recursiva.
Não diminuir o problema na chamada recursiva (passar o mesmo n).
Esperar que a recursão seja "de graça": ela gasta memória da pilha.
Usar Fibonacci recursivo ingênuo para n grande (é exponencial!).
Confundir o valor de retorno dos casos base (ex.: fatorial(0) é 1, não 0; soma_ate(0) é 0).
Estouro do tipo: fatorial(25) já não cabe num long. Recursão correta, tipo pequeno demais.

👥 Quarta — Encontro¶

Chegue ao encontro tendo estudado o material e tendo executado os exemplos. Traga suas dúvidas sobre "por que a recursão funciona" — é o ponto que mais gera perguntas, e o encontro é o momento ideal para dissipá-las. Roteiro previsto:

Revisão relâmpago: os dois elementos (caso base e caso recursivo) e a pilha de chamadas.
Simulação ao vivo: vamos executar fatorial(4) e fib(4) no quadro, desenhando a pilha empilhar e desempilhar, chamada por chamada.
Galeria de erros: provocamos de propósito uma recursão infinita para ver o stack overflow acontecer, e discutimos como diagnosticá-lo.
Construção guiada: transformamos, juntos, uma função iterativa numa recursiva (e vice-versa).

Problema-guia do encontro — soma dos dígitos: dado um inteiro não-negativo, calcular a soma dos seus dígitos de forma recursiva. Por exemplo, soma_digitos(1234) deve dar 1 + 2 + 3 + 4 = 10. A ideia: o último dígito é n % 10, e o "resto do número" é n / 10 (divisão inteira, Semana 01).

soma_digitos.c

#include <stdio.h>

int soma_digitos(int n) {
    if (n == 0) {                    // caso base: nao ha mais digitos
        return 0;
    }
    return (n % 10) + soma_digitos(n / 10);   // ultimo digito + resto
}

int main(void) {
    int n;
    printf("Digite um inteiro nao-negativo: ");
    scanf("%d", &n);
    printf("Soma dos digitos: %d\n", soma_digitos(n));
    return 0;
}

Perguntas para pensar antes do encontro: por que o caso base é n == 0? O que faz n / 10 "encolher" o problema a cada chamada? Desenhe a pilha de soma_digitos(1234).

✍️ Sexta — Estudo dirigido¶

Reserve este tempo para praticar de verdade. Recursão se aprende escrevendo e, principalmente, simulando no papel quando algo não sai como esperado.

Exercícios guiados (Beecrowd)¶

Crie/entre na sua conta no Beecrowd e resolva, em C. Todos podem (e alguns devem) ser resolvidos com recursão:

Nº	Problema	O que exercita
1151	Fibonacci Fácil	imprimir termos de Fibonacci (compare recursivo × iterativo)
1153	Fatorial Simples	fatorial — resolva de forma recursiva
1161	Soma de Fatoriais	reutilizar `fatorial` recursivo dentro de uma soma

Os números e nomes acima seguem a numeração usual do Beecrowd. Se algum diferir na plataforma, procure pelo tipo do problema (Fibonacci, fatorial, soma de fatoriais) na trilha de iniciantes.

Desafios para escrever do zero¶

Fatorial recursivo: implemente long fatorial(int n) e teste com vários valores. A partir de que n o resultado "estoura" o long?
Soma de dígitos recursiva: o problema-guia do encontro (soma_digitos), feito por você, sem olhar.
Potência recursiva: long potencia(int base, int exp) para exp >= 0.
Máximo divisor comum (MDC) pela recursão de Euclides: o algoritmo de Euclides é naturalmente recursivo — mdc(a, b) = mdc(b, a % b), com caso base mdc(a, 0) = a:
```
int mdc(int a, int b) {
    if (b == 0) {          // caso base
        return a;
    }
    return mdc(b, a % b);  // caso recursivo
}
```
Digite, execute e entenda por que a % b faz o problema encolher.
Imprimir um número ao contrário: dado 1234, imprimir 4 3 2 1 recursivamente. (Dica: imprima n % 10 antes da chamada recursiva com n / 10.)
Torres de Hanói: implemente a função hanoi da seção 7 e conte quantos movimentos ela imprime para n = 3, n = 4 e n = 5. Percebe o padrão?

Para investigar (curiosidade prática)¶

Recursivo × iterativo, na prática: implemente fib recursivo e fib iterativo. Adicione um contador global de chamadas ao recursivo e imprima quantas chamadas ele faz para n = 10, 20, 30. Cronometre também. O que você conclui sobre o custo?
Removendo o caso base: pegue o seu fatorial recursivo e comente a linha do caso base. Rode e observe o que acontece (provavelmente um Segmentation fault). Explique, com base na pilha de chamadas, por quê.

✅ Checklist de autoavaliação¶

Marque com sinceridade — se algum item não estiver ✅, volte à seção correspondente.

Explico, com minhas palavras, o que é uma função recursiva e dou exemplos.
Sei apontar o caso base e o caso recursivo de uma função recursiva.
Consigo simular no papel fatorial(4), vendo a pilha empilhar e desempilhar.
Escrevo recursões corretas para fatorial, soma, potência, Fibonacci e MDC.
Sei converter entre uma versão recursiva e uma iterativa.
Reconheço as causas de uma recursão infinita e sei o que é estouro de pilha.
Explico por que o Fibonacci recursivo ingênuo é exponencialmente lento.
Sei quando a recursão vale a pena e quando um laço é a melhor escolha.

🔗 Referências e para se aprofundar¶

Material 2026.1 — Aula 13: Recursão.
BACKES, André. Linguagem C: completa e descomplicada (capítulo sobre recursão e funções recursivas).
KERNIGHAN, B.; RITCHIE, D. The C Programming Language (o clássico "K&R"), cap. 4 (seção sobre recursão).
Referência: cppreference — funções em C.
Prática: Beecrowd.

Antes de seguir para a Semana 07

A recursão é, ao mesmo tempo, um jeito de pensar ("resolva o caso pequeno, depois combine") e uma técnica de programação. Não se preocupe se ela ainda parecer estranha — a intuição vem com a prática de desenhar a pilha. Na próxima semana entramos nos vetores (arrays): a primeira forma de guardar muitos valores numa única variável. Lá você verá que percorrer um vetor com um laço é o pão de cada dia — e que recursão e vetores, juntos, abrem as portas para os algoritmos de busca e ordenação que dominam boa parte da computação.