O que é recursão?

Recursão é uma técnica de programação onde uma função chama a si mesma para resolver versões menores de um problema. Essa abordagem é inspirada no conceito matemático de definição recursiva e é especialmente útil para problemas que podem ser decompostos em subproblemas similares. Uma função recursiva sempre contém pelo menos um caso base, que interrompe a recursão, e um passo recursivo, que reduz o problema original.

Por exemplo, o cálculo do fatorial de um número inteiro n pode ser definido recursivamente: fatorial(0) = 1, fatorial(n) = n * fatorial(n-1). Observe que a cada chamada o argumento n diminui, garantindo que eventualmente atingimos o caso base n=0.

Componentes essenciais

Para escrever uma função recursiva correta, precisamos de três elementos:

  • Caso base: a condição mais simples que pode ser resolvida sem recursão. Sem ele, a função nunca termina.
  • Passo recursivo: a chamada recursiva que resolve um subproblema menor. O argumento passado deve se aproximar do caso base.
  • Progressão: a cada chamada, o tamanho do problema deve diminuir, assegurando a terminação.

Um exemplo prático é a implementação da busca binária em um array ordenado. A função recebe o array, os índices esquerdo e direito e o valor alvo. O caso base ocorre quando o intervalo está vazio; caso contrário, calcula-se o ponto médio e decide-se se a busca continua na metade esquerda ou direita, reduzindo o intervalo pela metade a cada passo.

Exemplos clássicos

A seguir, alguns exemplos que ilustram a recursão em ação:

Fatorial

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

Fibonacci

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

Embora simples, a implementação recursiva de Fibonacci tem complexidade O(2^n) e não é recomendada para n grandes sem otimização.

Busca binária

def busca_binaria(arr, esq, dir, alvo):
    if esq > dir:
        return -1
    meio = (esq + dir) // 2
    if arr[meio] == alvo:
        return meio
    elif arr[meio] < alvo:
        return busca_binaria(arr, meio + 1, dir, alvo)
    else:
        return busca_binaria(arr, esq, meio - 1, alvo)

Torres de Hanói

O problema das Torres de Hanói consiste em mover uma pilha de discos de um pino para outro, usando um pino auxiliar, com a regra de que um disco maior nunca pode ficar sobre um menor. A solução recursiva é elegante:

def hanoi(n, origem, destino, auxiliar):
    if n == 1:
        print("Move disco 1 de", origem, "para", destino)
    else:
        hanoi(n - 1, origem, auxiliar, destino)
        print("Move disco", n, "de", origem, "para", destino)
        hanoi(n - 1, auxiliar, destino, origem)

Recursão vs Iteração

Recursão e iteração são duas maneiras de implementar repetição. A iteração utiliza estruturas de loop (for, while) e mantém o estado em variáveis. A recursão utiliza chamadas de função e a pilha de execução para gerenciar o estado.

Vantagens da recursão:

  • Código mais próximo da definição matemática, facilitando a compreensão para problemas recursivos.
  • Natural para estruturas de dados recursivas como árvores e listas encadeadas.

Desvantagens:

  • Maior consumo de memória devido à pilha de chamadas.
  • Risco de estouro de pilha para profundidades grandes.
  • Overhead de chamada de função pode tornar a execução mais lenta.

Na prática, a escolha entre recursão e iteração depende do problema e da linguagem. Para problemas com profundidade conhecida e pequena, a recursão é perfeitamente aceitável. Para problemas que exigem muitas iterações, a iteração costuma ser mais eficiente.

Boas práticas e cuidados

Ao trabalhar com recursão, lembre-se dos seguintes pontos:

  • Defina sempre um caso base claro e alcançável.
  • Verifique se a recursão progride em direção ao caso base.
  • Evite recursão excessivamente profunda; se a profundidade esperada for grande, considere usar iteração.
  • Em linguagens que suportam, prefira tail recursion para permitir otimização pelo compilador.
  • Teste com entradas pequenas antes de aplicar em produção.

Resumo

  • Recursão é uma técnica onde uma função chama a si mesma.
  • Os elementos essenciais são caso base e passo recursivo.
  • Exemplos clássicos incluem fatorial, Fibonacci, busca binária e Torres de Hanói.
  • Recursão pode ser mais clara, mas consome mais recursos que iteração.
  • Tail recursion pode ser otimizada em algumas linguagens.

Perguntas Frequentes

Quando devo usar recursão?

Use recursão quando o problema puder ser decomposto naturalmente em subproblemas do mesmo tipo, como travessia de árvores, algoritmos de divisão e conquista (mergesort, quicksort) e processamento de expressões recursivas.

Recursão é mais lenta que iteração?

Normalmente, recursão tem overhead de chamada de função e pilha. Entretanto, com otimizações como tail recursion, a diferença pode ser reduzida. Para problemas recursivos profundos, a iteração pode ser mais rápida e segura.

Como evitar estouro de pilha?

Limite a profundidade da recursão. Se a profundidade for imprevisível ou grande, converta o algoritmo para iterativo. Em alguns casos, é possível aumentar o tamanho da pilha, mas essa não é uma solução recomendada.