Funções recursivas

O problema

Você quer saber quantos arquivos existem na pasta Documentos. Ela tem alguns arquivos e algumas subpastas. Cada subpasta pode ter mais arquivos e mais subpastas, sem limite de profundidade. Uma quantidade fixa de laços for aninhados não resolve, porque você não sabe quantos níveis existem. (Dá para resolver com um laço e uma pilha montada à mão, mas a recursão é o caminho mais direto e é o que vamos estudar.)

Como repetir a mesma estratégia em cada subpasta e saber quando parar?

Pense em como você faria à mão: “o total de Documentos é o número de arquivos soltos nela mais o total de cada subpasta”. Para saber o total de uma subpasta, você aplica a mesma regra. Quando chega a uma pasta sem subpastas, a resposta é imediata. Uma regra que usa a si mesma em um problema menor é uma recursão. Vamos implementar exatamente esse problema mais adiante. Antes, um exemplo menor para enxergar o mecanismo.

Conceitos centrais

Uma função recursiva chama a si mesma com uma versão menor do problema, até chegar a um caso que sabe responder diretamente.

Caso base

O caso pequeno o bastante para responder sem nova chamada, como uma pasta sem subpastas. É ele que faz a recursão parar.

Redução

Transforma o problema em problemas menores, como cada subpasta em vez da pasta inteira.

Junção

Junta as respostas menores para montar a resposta atual. No exemplo: arquivos soltos + total de cada subpasta.

Pilha

Cada chamada em andamento fica guardada na memória, esperando a resposta das chamadas que ela fez.

A pilha de chamadas

O exemplo mais simples possível: somar os números de 1 até n. A soma de 1 a 4 é 4 + (soma de 1 a 3), e assim por diante, até a soma de 1 a 0, que é 0.

#include <stdio.h>

// Pré-condição: n >= 0 (com n negativo, nunca chega ao caso base).
int soma(int n) {
    if (n == 0) return 0;          // caso base
    return n + soma(n - 1);        // redução + junção
}

int main(void) {
    printf("%d\n", soma(4));
    return 0;
}

Saída: 10

O comentário “Pré-condição” no código diz o que precisa ser verdade antes de chamar a função para que ela funcione. Aqui, n não pode ser negativo.

O que acontece por baixo é o que mais confunde quem está começando, e a figura mostra passo a passo:

Cada chamada em espera ocupa um pedaço da pilha, uma área de memória pequena (cerca de 1 MB no Windows e 8 MB no Linux, por padrão). Por isso, uma recursão muito profunda trava o programa, mesmo com um caso base correto. Nos testes desta aula (Windows, compilador MSVC sem otimizações, pilha padrão de 1 MB), soma(10000) funcionou, e soma(50000) terminou com stack overflow. O limite exato muda com o sistema, o compilador e as opções de compilação, e o tamanho da pilha pode ser configurado. Para somar 50 mil números, um laço for é a escolha certa.

Exemplo real: contar arquivos em pastas

Agora o problema do início. Cada pasta é uma struct com o número de arquivos soltos e ponteiros para as subpastas. É a junção das duas aulas anteriores.

#include <stdio.h>

typedef struct Pasta {
    const char *nome;
    int arquivos;               // arquivos diretamente nesta pasta
    int qtd_sub;                // quantas subpastas ela tem
    struct Pasta *sub[4];       // ponteiros para as subpastas
} Pasta;
// Pré-condições: 0 <= qtd_sub <= 4, ponteiros válidos e nenhuma pasta
// contida em si mesma (sem ciclos), senão a recursão nunca termina.

int contar(const Pasta *p) {
    int total = p->arquivos;                  // arquivos soltos
    for (int i = 0; i < p->qtd_sub; i++) {
        total += contar(p->sub[i]);           // mesma regra em cada subpasta
    }
    return total;
}

int main(void) {
    Pasta viagem = {"Viagem", 3, 0, {0}};
    Pasta fotos  = {"Fotos", 5, 1, {&viagem}};
    Pasta relat  = {"Relatorios", 4, 0, {0}};
    Pasta trab   = {"Trabalho", 1, 1, {&relat}};
    Pasta docs   = {"Documentos", 2, 2, {&fotos, &trab}};

    printf("Total de arquivos: %d\n", contar(&docs));
    return 0;
}

Saída: Total de arquivos: 15

Repare que contar não sabe, e não precisa saber, quantos níveis a árvore tem. Ela funciona igual para 2 ou 200 níveis. Esse tipo de estrutura, em que cada item contém outros itens do mesmo tipo, aparece em todo lugar: pastas, menus com submenus, comentários com respostas, organogramas, o HTML desta página. Recursão é a ferramenta natural para percorrê-los.

Padrões recursivos

Muitos problemas recursivos de prova ou de entrevista se encaixam em um destes formatos. Reconhecer o formato é metade da solução.

1. Reduzir de um em um

Uma chamada por vez, cada uma com um problema uma unidade menor: soma, fatorial, contagem regressiva. É fácil de escrever, mas faz uma chamada por elemento. Para listas grandes, prefira um laço.

2. Uma chamada para cada filho

Pastas, menus, organogramas: a função se chama uma vez para cada item interno, como em contar. O número total de chamadas é igual ao número de itens da estrutura, sem desperdício.

3. Cortar pela metade: busca binária

Pense em procurar uma palavra no dicionário. Você não lê página por página: abre no meio, vê se a palavra vem antes ou depois e descarta metade do livro. Depois repete na metade que sobrou. Em um vetor ordenado, a busca binária faz exatamente isso:

// Procura alvo em v[ini..fim], vetor em ordem crescente. Retorna a posição ou -1.
int busca_binaria(const int v[], int ini, int fim, int alvo) {
    if (ini > fim) return -1;                    // não sobrou nada: não existe
    int meio = ini + (fim - ini) / 2;
    if (v[meio] == alvo) return meio;            // achou
    if (v[meio] < alvo)
        return busca_binaria(v, meio + 1, fim, alvo);   // só pode estar à direita
    return busca_binaria(v, ini, meio - 1, alvo);       // só pode estar à esquerda
}

O ganho é enorme na prática. Nos testes desta aula, o pior caso foi:

Cada vez que a lista dobra de tamanho, a busca binária precisa de só um passo a mais. A condição é que a lista esteja ordenada, e é para isso que servem as próximas três aulas.

E onde está a recursão? Cada passo da figura é uma chamada de busca_binaria. Para achar o 72, a pilha chega a ter no máximo 4 chamadas abertas, uma por passo. Para 1 milhão de nomes, seriam no máximo 20.

4. Duas chamadas que se repetem: Fibonacci Aprofundamento

Na sequência de Fibonacci (0, 1, 1, 2, 3, 5, 8, 13…), cada número é a soma dos dois anteriores. A tradução direta para C é curta e elegante, e muito lenta:

long long fib_ingenuo(int n) {
    if (n < 2) return n;
    return fib_ingenuo(n - 1) + fib_ingenuo(n - 2);
}

A solução é anotar cada resposta na primeira vez que ela é calculada e consultar a anotação nas vezes seguintes. Essa técnica se chama memoização:

long long memo[91];           // global: começa zerado; fib(90) ainda cabe em long long

long long fib(int n) {        // Pré-condição: 0 <= n <= 90.
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];     // já calculado: só consulta
    memo[n] = fib(n - 1) + fib(n - 2);    // calcula uma vez e anota
    return memo[n];
}

Com a anotação, fib(40) faz 79 chamadas em vez de 331 milhões, e fib(90), que na versão ingênua levaria séculos, faz 179 chamadas e responde na hora. Repare no padrão: na primeira chamada, com a tabela memo ainda zerada e n ≥ 1, fib(n) faz exatamente 2n − 1 chamadas. Se a tabela já tiver valores anotados de chamadas anteriores, faz menos. Cada valor de 2 a n é calculado uma única vez e consulta a tabela no máximo uma vez, então o trabalho cresce junto com n, e não explode.

5. Testar todas as escolhas: backtracking Aprofundamento

Uma pizzaria quer listar todas as pizzas possíveis com três ingredientes opcionais. Para cada ingrediente, há duas escolhas: colocar ou não colocar. A recursão decide um ingrediente por nível e, ao voltar, experimenta a outra opção:

Agora o código. Repare na linha escolhido[i] = 0;: é o momento em que a recursão volta a um nó da árvore e pega o outro ramo.

#include <stdio.h>

const char *ingredientes[] = {"queijo", "calabresa", "cebola"};

// i: qual ingrediente está sendo decidido; escolhido[k] = 1 se o k-ésimo entrou.
void montar(int i, int escolhido[]) {
    if (i == 3) {                               // decidiu todos: imprime a pizza
        printf("Pizza:");
        int vazia = 1;
        for (int k = 0; k < 3; k++) {
            if (escolhido[k]) { printf(" %s", ingredientes[k]); vazia = 0; }
        }
        if (vazia) printf(" so massa");
        printf("\n");
        return;
    }
    escolhido[i] = 1;            // escolha 1: COM o ingrediente i
    montar(i + 1, escolhido);
    escolhido[i] = 0;            // escolha 2: SEM o ingrediente i (desfaz)
    montar(i + 1, escolhido);
}

int main(void) {
    int escolhido[3];
    montar(0, escolhido);
    return 0;
}

Esse padrão resolve problemas como gerar senhas, montar escalas de trabalho e escolher itens para caber em uma mochila. É a base do desafio hacker desta aula.

Quanto custa uma recursão? Aprofundamento

Não é preciso fórmula para ter uma boa estimativa. Faça duas perguntas:

1. Quantas chamadas vão acontecer no total, e quanto trabalho cada uma faz? É o que define o tempo. Desenhe a árvore para uma entrada pequena e veja como ela cresce. Cuidado com o trabalho por chamada: as 8 pizzas são 8 folhas, mas imprimir cada uma percorre os ingredientes.
2. Quantas chamadas ficam abertas ao mesmo tempo? É o que define a memória da pilha: a altura da árvore, e não o total.

Nas próximas aulas, esses comportamentos ganham nomes: O(n) para “cresce junto com a entrada”, O(log n) para “corta pela metade” e O(2ⁿ) para “dobra a cada item”. A intuição da tabela vale mais que a notação.

Exercícios progressivos

Para cada exercício, desenhe a pilha ou a árvore de chamadas antes de escrever código, como nas figuras da aula. A dica não entrega a resposta: ela indica a pergunta certa a fazer.

void contagem(int n) {
    if (n == 0) {
        printf("Lancar!\n");
        return;
    }
    printf("%d ", n);
    contagem(n - 1);
}

void contagem(int n) {
    if (n <= 0) {               // cobre 0 e qualquer negativo
        printf("Lancar!\n");
        return;
    }
    printf("%d ", n);
    contagem(n - 1);
}

void ida(int n)   { if (n == 0) return; printf("%d ", n); ida(n - 1); }
void volta(int n) { if (n == 0) return; volta(n - 1); printf("%d ", n); }
void ambos(int n) { if (n == 0) return; printf("%d ", n); ambos(n - 1); printf("%d ", n); }

int fatorial(int n) {
    if (n == 0) return 1;            // 0 grupos: 1 ordem (a vazia)
    return n * fatorial(n - 1);      // n escolhas para o 1º, vezes o resto
}

int profundidade(const Pasta *p) {
    int maior = 0;                              // maior profundidade entre as subpastas
    for (int i = 0; i < p->qtd_sub; i++) {
        int d = profundidade(p->sub[i]);
        if (d > maior) maior = d;
    }
    return 1 + maior;                           // a própria pasta conta como 1 nível
}

void hanoi(int n, char origem, char destino, char aux) {
    if (n == 0) return;                          // nenhum disco: nada a fazer
    hanoi(n - 1, origem, aux, destino);          // 1) tira os n-1 menores do caminho
    printf("disco %d: %c -> %c\n", n, origem, destino);   // 2) move o maior
    hanoi(n - 1, aux, destino, origem);          // 3) coloca os n-1 sobre o maior
}