Durante nossas aulas de hoje, vamos abordar um dos tópicos mais importantes dentro da disciplina de algoritmos: a recursão. É um conceito que, à primeira vista, pode parecer um pouco confuso, mas depois que você entende a lógica por trás, se torna uma ferramenta extremamente poderosa.

O que é Recursão?

Recursão é uma técnica onde uma função invoca a si mesma para resolver um problema. A ideia central é dividir um problema grande em problemas menores e mais simples, até que se atinja um ponto onde a solução seja trivial. Esse ponto é conhecido como caso base.

Caso Base e Caso Recursivo

Toda função recursiva precisa ter dois elementos essenciais:

  • Caso Base: A condição que interrompe a recursão. Sem ele, a função se chamaria infinitamente, resultando em um RecursionError no Python.
  • Caso Recursivo: A chamada da função a ela mesma, geralmente com um conjunto de dados reduzido, aproximando-se do caso base a cada execução.

Exemplo Clássico: Fatorial

O cálculo do fatorial de um número é o "Hello World" da recursão. Matematicamente, n! = n * (n-1)!, com 0! = 1.

def fatorial(n):
    if n == 0:  # Caso base
        return 1
    return n * fatorial(n - 1)  # Caso recursivo

Quando chamamos fatorial(5), a pilha de chamadas (call stack) ganha um novo frame para cada chamada: fatorial(5) → fatorial(4) → fatorial(3) → fatorial(2) → fatorial(1) → fatorial(0). Ao atingir o caso base, os retornos se propagam: 1, 1*1=1, 2*1=2, 3*2=6, 4*6=24, 5*24=120.

Recursão em Cauda (Tail Recursion)

Um conceito avançado é a recursão em cauda, onde a chamada recursiva é a última operação da função. Em linguagens funcionais, isso permite otimizações onde o compilador reutiliza o stack frame, evitando o crescimento da pilha. O Python não implementa essa otimização (TCO - Tail Call Optimization), mas é um bom exercício mental tentar escrever funções nesse estilo.

Recursão vs Iteração

Muitos problemas podem ser resolvidos tanto com recursão quanto com iteração (loops). A escolha depende do contexto e da legibilidade.

  • Vantagens da Recursão: Código mais limpo e expressivo para problemas como travessia de árvores, algoritmos de dividir e conquistar (Merge Sort, Quick Sort) e problemas que têm uma definição naturalmente recursiva, como as Torres de Hanói.
  • Desvantagens: Maior consumo de memória (stack frames) e risco de estouro de pilha para entradas muito grandes. O limite padrão de recursão no Python é 1000, ajustável com sys.setrecursionlimit(). A iteração tende a ser mais performática em linguagens imperativas como Python, pois evita o overhead de chamada de função.

Complexidade e Memoização

Um cuidado importante ao usar recursão é evitar a explosão exponencial. O cálculo do Fibonacci ingênuo é um exemplo clássico:

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

Este código recalcula os mesmos valores inúmeras vezes, resultando em complexidade O(2^n). Para resolver isso, podemos usar memoização (armazenar resultados já calculados em um dicionário) ou programação dinâmica.

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

Aplicações Práticas: Torres de Hanói

Um problema clássico que se resolve de forma elegante com recursão são as Torres de Hanói. A lógica é:

  • Mover N-1 discos da torre A para a torre B (usando C como auxiliar).
  • Mover o último disco (maior) da torre A para a torre C.
  • Mover N-1 discos da torre B para a torre C (usando A como auxiliar).

A implementação recursiva é surpreendentemente curta e reflete exatamente essa lógica.

Aplicações em Grafos: DFS

A recursão também é a base para algoritmos de busca em profundidade (DFS - Depth First Search).

def dfs(grafo, no, visitados=None):
    if visitados is None:
        visitados = set()
    visitados.add(no)
    for vizinho in grafo[no]:
        if vizinho not in visitados:
            dfs(grafo, vizinho, visitados)
    return visitados

Este algoritmo recursivo percorre todo o grafo sem a necessidade de uma pilha explícita, pois a pilha de chamadas faz esse papel.

Conclusão

A recursão é um dos pilares da computação. Dominar esse conceito abre portas para entender estruturas de dados complexas (árvores, grafos), algoritmos de busca e ordenação, e até mesmo linguagens de programação funcionais. Não se preocupe se não ficar claro de primeira; a prática leva à perfeição. Recomendo implementar os exemplos acima no seu ambiente de desenvolvimento e brincar com o debugger para visualizar a pilha de chamadas. Veja mais artigos aqui.

Perguntas Frequentes

  1. O que acontece se o caso base não for definido? A função entrará em um loop infinito, e o programa eventualmente lançará um erro RecursionError: maximum recursion depth exceeded.
  2. Qual é a diferença entre recursão direta e indireta? Na recursão direta, a função chama a si mesma (ex: fatorial). Na recursão indireta, a função A chama a função B, que por sua vez chama a função A.
  3. É possível converter qualquer algoritmo iterativo em recursivo? Sim, qualquer algoritmo que pode ser implementado com iteração pode ser implementado com recursão, e vice-versa. A escolha geralmente se baseia na legibilidade e na performance.
  4. Recursão gasta mais memória que iteração? Sim, porque cada chamada recursiva adiciona um novo frame à pilha de chamadas, consumindo memória extra para variáveis locais e endereços de retorno. Esse é o famoso overhead da recursão.