Funções — Avançado

Recursão é como dois espelhos se enfrentando — imagens se aninham dentro de si mesmas até que o ponto distante de luz se dissipe. Uma função que chama a si mesma resolve problemas através desse poder de redução progressiva.

Princípios da recursão

Recursão é uma técnica de programação onde uma função chama a si mesma direta ou indiretamente. Toda recursão deve ter dois elementos:

1. Condição recursiva: o problema pode ser decomposto em subproblemas menores do mesmo tipo
2. Caso base (condição de terminação): o menor subproblema tem uma resposta direta e não recursa mais

int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

Tomando factorial(4) como exemplo, o processo de execução:

factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1
= 24

Exemplos clássicos de recursão

Fatorial

A definição de n fatorial: n! = n x (n-1)!, e 0! = 1.

long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Note que o tipo long tem alcance limitado; factorial(20) já está próximo do limite de 64 bits.

Sequência de Fibonacci

Definição de Fibonacci: F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2).

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

Torre de Hanói

Mova n discos da estaca A para a estaca C, usando a estaca B como auxiliar. Regra: um disco maior não pode ser colocado sobre um menor.

#include <stdio.h>

void hanoi(int n, char from, char mid, char to) {
    if (n == 1) {
        printf("%c -> %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, to, mid);
    printf("%c -> %c\n", from, to);
    hanoi(n - 1, mid, from, to);
}

int main(void) {
    hanoi(3, 'A', 'B', 'C');
    return 0;
}

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

A ideia: primeiro mova os n-1 discos superiores para a estaca auxiliar, mova o maior disco para a estaca destino, depois mova os n-1 discos da estaca auxiliar para a estaca destino. 3 discos exigem 7 movimentos; n discos exigem 2^n - 1 movimentos.

Exemplo

Compute recursivamente a soma dos dígitos de um inteiro:

#include <stdio.h>

int digit_sum(int n) {
    if (n < 10) return n;
    return n % 10 + digit_sum(n / 10);
}

int main(void) {
    printf("%d\n", digit_sum(12345));
    printf("%d\n", digit_sum(7));
    return 0;
}

15
7

digit_sum(12345) = 5 + digit_sum(1234) = 5 + 4 + digit_sum(123) = ... = 5+4+3+2+1 = 15.

Escopo de variáveis

O escopo determina quais regiões do código podem ver e usar uma variável.

Escopo de bloco

Variáveis definidas dentro de {} são visíveis apenas dentro daquele bloco e são destruídas quando o bloco termina:

int main(void) {
    int x = 10;
    {
        int y = 20;
        printf("%d %d\n", x, y);
    }
    printf("%d\n", x);
    return 0;
}

y existe apenas no bloco interno e não pode ser acessado do bloco externo.

Escopo de arquivo

Variáveis definidas fora de todas as funções têm escopo de arquivo e são visíveis de sua definição até o final do arquivo. Essas são chamadas variáveis globais:

int count = 0;

void increment(void) {
    count++;
}

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

Sombreamento de nomes

Uma variável em um escopo interno sombra uma variável com o mesmo nome em um escopo externo:

int x = 100;

int main(void) {
    int x = 10;
    printf("%d\n", x);
    return 0;
}

A saída é 10; o x interno sombreia o x global. O x global não pode ser acessado diretamente dentro do bloco interno.

Classes de armazenamento

Classes de armazenamento determinam o tempo de vida e a visibilidade de uma variável. C tem quatro palavras-chave de classe de armazenamento: auto, static, extern e register.

auto

auto é a classe de armazenamento padrão para variáveis locais e geralmente é omitida. As variáveis são criadas ao entrar no bloco e destruídas ao sair:

void func(void) {
    auto int x = 10;
}

Isso equivale a int x = 10;.

static

Quando static modifica uma variável local, a variável existe durante toda a execução do programa, mas seu escopo permanece limitado à função. Propriedade-chave: é inicializada apenas uma vez, e chamadas subsequentes retêm o valor anterior.

#include <stdio.h>

void counter(void) {
    static int count = 0;
    count++;
    printf("Call #%d\n", count);
}

int main(void) {
    counter();
    counter();
    counter();
    return 0;
}

Call #1
Call #2
Call #3

Sem static, count seria reinicializado com 0 a cada chamada, sempre imprimindo "Call #1".

Quando static modifica uma variável global ou função, restringe sua visibilidade ao arquivo atual (ligação interna); outros arquivos fonte não podem acessá-la via extern.

extern

extern declara uma variável global definida em outro arquivo fonte, dizendo ao compilador "esta variável existe, mas não está definida no arquivo atual":

arquivo1.c:

int shared_data = 42;

arquivo2.c:

#include <stdio.h>

extern int shared_data;

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

extern não aloca memória; é apenas uma declaração. Projetos com múltiplos arquivos precisam de extern para compartilhar dados globais.

register

register sugere ao compilador que armazene a variável em um registrador da CPU para acesso mais rápido:

void fast_loop(void) {
    register int i;
    for (i = 0; i < 1000000; i++) {
    }
}

Compiladores modernos são muito bons em otimização e tipicamente colocam variáveis frequentemente usadas em registradores automaticamente, então a dica register tem pouco efeito. Nota: você não pode obter o endereço de uma variável register (&), porque registradores não têm endereços de memória.

Exemplo

Fibonacci iterativa usando um laço (evitando a computação repetida da recursão):

#include <stdio.h>

long fib_iter(int n) {
    if (n <= 2) return 1;
    long prev = 1;
    long curr = 1;
    long next;
    int i;

    for (i = 3; i <= n; i++) {
        next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    int i;
    for (i = 1; i <= 10; i++) {
        printf("F(%d) = %ld\n", i, fib_iter(i));
    }
    return 0;
}

F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55

Esta versão iterativa tem complexidade de tempo O(n), muito melhor que a O(2^n) da recursão ingênua.

❓ Perguntas Frequentes

P: O que é melhor, recursão ou laços? R: Laços são geralmente mais eficientes; recursão é mais intuitiva para certos problemas. Prefira laços para casos simples; use recursão para estruturas naturalmente recursivas como percurso de árvores.

P: Onde na memória as variáveis locais estáticas são armazenadas? R: Na área de armazenamento estático (segmento de dados), na mesma região que variáveis globais, não na pilha.

P: Qual a diferença entre uma declaração extern e uma definição de variável? R: Uma definição aloca memória e pode inicializar; uma declaração extern não aloca memória, apenas informa que a variável está definida em outro lugar. Uma variável só pode ser definida uma vez, mas declarada múltiplas vezes.

P: Variáveis register são realmente mais rápidas? R: Compiladores modernos realizam automaticamente a otimização de alocação de registradores. register explícito quase não tem efeito adicional; essa palavra-chave tem principalmente significado histórico.

📖 Resumo

• Recursão deve incluir um caso base, ou a pilha transbordará
• Fibonacci recursiva ingênua é ineficiente; problemas reais precisam de laços ou memoização
• Variáveis locais têm escopo de bloco; variáveis globais têm escopo de arquivo
• Variáveis locais estáticas persistem durante todo o programa, mas seu escopo permanece inalterado
• extern permite compartilhamento de variáveis entre arquivos; register tem pouco significado em compiladores modernos

📝 Exercícios

1. Escreva uma função recursiva void print_reverse(int n) que imprima os dígitos de um inteiro positivo em ordem inversa (ex.: 123 imprime 3 2 1).
2. Escreva uma função que use uma variável estática para contar quantas vezes foi chamada. Chame-a 5 vezes em main, depois imprima a contagem.
3. Implemente busca binária recursiva: busque um valor alvo em um vetor ordenado; retorne o índice se encontrar, ou -1 se não encontrar.