Durante a aula de hoje, mergulhamos no conceito de recursão – uma técnica fundamental na ciência da computação onde uma função chama a si mesma para resolver versões menores de um problema, até atingir uma condição de parada. A recursão aparece em algoritmos de ordenação, travessia de árvores, problemas combinatórios e até mesmo na definição de certas estruturas de dados. Vou registrar aqui os principais pontos discutidos.

1. O que é recursão?

Uma função recursiva é definida em termos de si mesma. A ideia central é quebrar um problema maior em subproblemas mais simples (passo recursivo) e parar quando o problema se torna trivial (caso base). Sem um caso base, a função continuaria chamando a si mesma indefinidamente, causando um estouro de pilha (stack overflow).

Exemplo simples (contagem regressiva em Python):

def contagem(n):
    if n == 0:           # caso base
        print("Fim!")
    else:
        print(n)
        contagem(n - 1)  # passo recursivo

A cada chamada, o problema se aproxima do caso base. Essa estrutura é a marca registrada de qualquer função recursiva bem formada.

2. Pilha de chamadas e profundidade

Quando uma função recursiva executa, cada chamada é empilhada na pilha de chamadas (call stack). O sistema operacional aloca um quadro de pilha para armazenar variáveis locais e o endereço de retorno. Se a recursão for muito profunda (milhares de chamadas), a pilha pode transbordar – é o famoso RecursionError em Python ou StackOverflowException em outras linguagens.

A profundidade máxima depende da linguagem e do ambiente. Em Python, o limite padrão é 1000 (ajustável com sys.setrecursionlimit). Em linguagens compiladas como C, a pilha é fixa e estourá-la pode causar um crash. Por isso, é importante conhecer o tamanho do problema antes de optar pela recursão.

3. Exemplos clássicos

Vimos três exemplos que a maioria dos cursos apresenta:

3.1 Fatorial

def fatorial(n):
    if n == 0 or n == 1:
        return 1
    return n * fatorial(n - 1)

Matematicamente, n! = n × (n‑1)!. A recursão segue naturalmente a definição.

3.2 Sequência de Fibonacci

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

Embora simples, essa implementação tem complexidade exponencial – cada chamada gera duas novas chamadas. Mostra que recursão nem sempre é a melhor solução; para Fibonacci, iteração ou programação dinâmica são mais eficientes.

3.3 Torres de Hanói

def hanoi(n, origem, destino, auxiliar):
    if n == 1:
        print(f"Mova o disco 1 de {origem} para {destino}")
    else:
        hanoi(n-1, origem, auxiliar, destino)
        print(f"Mova o disco {n} de {origem} para {destino}")
        hanoi(n-1, auxiliar, destino, origem)

Esse problema ilustra perfeitamente a quebra recursiva: mover n-1 discos para o pino auxiliar, mover o maior disco para o destino e depois mover os n-1 discos do auxiliar para o destino.

4. Recursão versus Iteração

Recursão geralmente produz código mais legível e mais próximo da definição matemática. Por outro lado, pode consumir mais memória (pilha) e ser mais lenta devido ao overhead de chamadas de função. A iteração (for, while) usa apenas variáveis locais, sem empilhamento excessivo.

Existem técnicas para mitigar as desvantagens:

  • Recursão de cauda (tail recursion): quando a chamada recursiva é a última operação, alguns compiladores otimizam para iteração (eliminam a pilha).
  • Memoização: armazenar resultados de chamadas anteriores para evitar recomputação (ex.: Fibonacci com dicionário).

A escolha entre recursão e iteração depende do problema, da linguagem e da legibilidade desejada.

5. Dicas para escrever funções recursivas

Com base no que discutimos em sala, listo um passo‑a‑passo que ajuda a construir recursões corretas:

  • Identifique o caso base: qual a menor instância do problema? Quando ela pode ser resolvida trivialmente?
  • Defina o passo recursivo: como reduzir o problema atual em direção ao caso base? A chamada recursiva deve trabalhar com uma entrada menor.
  • Garanta progresso: a cada chamada, a entrada precisa se aproximar do caso base. Caso contrário, a recursão será infinita.
  • Teste com casos pequenos: simule manualmente com valores pequenos para verificar se a lógica está correta.
  • Cuidado com profundidade: se o problema exigir muitas chamadas aninhadas, prefira a versão iterativa ou aplique otimizações.

6. Recursão indireta

Um tópico interessante que surgiu foi a recursão indireta (ou mútua), onde duas ou mais funções se chamam entre si:

def par(n):
    if n == 0:
        return True
    return impar(n - 1)

def impar(n):
    if n == 0:
        return False
    return par(n - 1)

Embora menos comum, é útil em certos analisadores sintáticos (parsers) e na implementação de máquinas de estado.

Resumo dos pontos principais

  • Recursão resolve problemas dividindo‑os em subproblemas idênticos ao original, porém menores.
  • Toda função recursiva precisa de um caso base e de um passo recursivo que avance em direção a ele.
  • A pilha de chamadas limita a profundidade prática da recursão.
  • Recursão de cauda e memoização podem melhorar o desempenho.
  • Nem sempre a recursão é a melhor escolha – iteração pode ser mais rápida e econômica.

Perguntas frequentes (FAQ)

Quando devo usar recursão em vez de iteração?

Use recursão quando a definição natural do problema for recursiva (árvores, grafos, expressões matemáticas) e a profundidade de chamadas for pequena. Para loops simples ou quando o número de iterações é grande, a iteração é mais segura e eficiente.

O que é tail recursion e por que ela é importante?

Tail recursion ocorre quando a chamada recursiva é a última operação executada pela função. Linguagens com otimização de tail call convertem a recursão em iteração, reutilizando o mesmo quadro de pilha, evitando estouro. Python não implementa essa otimização nativamente, mas linguagens como Scheme e Lua o fazem.

Recursão pode causar vazamento de memória?

Não exatamente, mas cada chamada consome memória na pilha. Se a profundidade for excessiva, o programa pode travar. Após a função retornar, os quadros de pilha são liberados, portanto não há vazamento. Ferramentas como sys.getrecursionlimit() ajudam a monitorar o limite.