Hoje vamos mergulhar no conceito de recursão. Recursão é uma técnica de programação onde uma função chama a si mesma para resolver um problema. É uma ferramenta poderosa que permite escrever soluções elegantes para problemas que podem ser decompostos em subproblemas semelhantes ao original. Diferente da iteração, que usa laços explícitos (for, while), a recursão utiliza chamadas de função para repetir a computação.

O que é recursão?

Uma função recursiva é composta por dois elementos principais:

  • Caso base: a condição que interrompe a recursão. Sem ele, a função se chamaria infinitamente.
  • Passo recursivo: a parte onde a função se chama com um argumento modificado, aproximando-se do caso base.

Por exemplo, para calcular o fatorial de um número n, temos que n! = n × (n-1)!. O caso base é 0! = 1 (ou 1! = 1).

Exemplo 1: Fatorial

Vamos implementar uma função recursiva para calcular o fatorial em Python:

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

A cada chamada, n é reduzido em 1 até atingir o caso base. Visualize a pilha de chamadas para fatorial(4):

fatorial(4) → 4 * fatorial(3) → 4 * (3 * fatorial(2)) → 4 * (3 * (2 * fatorial(1))) → 4 * 3 * 2 * 1 = 24.

Exemplo 2: Sequência de Fibonacci

A sequência de Fibonacci é definida como F(0)=0, F(1)=1 e F(n)=F(n-1)+F(n-2) para n ≥ 2. Uma implementação recursiva direta é:

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

Essa abordagem é simples, mas extremamente ineficiente para valores grandes de n. Isso ocorre porque o mesmo cálculo é repetido muitas vezes (sobreposição de subproblemas). Por exemplo, fibonacci(5) calcula fibonacci(3) duas vezes. A complexidade temporal é O(2ⁿ).

Para otimizar, podemos usar memorização (memoization) ou programação dinâmica, guardando resultados já calculados.

Recursão vs Iteração

Tanto recursão quanto iteração podem resolver os mesmos problemas, mas cada uma tem vantagens e desvantagens:

  • Recursão tende a ser mais legível e intuitiva para problemas naturalmente recursivos (árvores, grafos, divisão e conquista).
  • Iteração geralmente é mais eficiente em termos de memória e velocidade, pois não há overhead de chamadas de função.
  • Linguagens funcionais otimizam recursão em cauda (tail recursion) para evitar estouro de pilha.

Na prática, escolha a abordagem que torne o código mais claro e mantenha a eficiência aceitável. Em Python, recursão tem um limite de profundidade padrão (~1000 chamadas), por isso iteração é preferível para loops longos.

Dicas para escrever funções recursivas

  1. Identifique o caso base: qual é a menor instância do problema que pode ser resolvida diretamente?
  2. Defina o passo recursivo: como reduzir o problema original em direção ao caso base?
  3. Certifique-se de que o passo recursivo converge: em cada chamada, o argumento deve se aproximar do caso base.
  4. Evite recursão muito profunda: se a profundidade esperada exceder o limite da linguagem, prefira iteração.
  5. Teste com exemplos pequenos para verificar se a função retorna o resultado esperado.

Perguntas Frequentes

1. Qual a diferença entre recursão e iteração?

Na iteração, o controle é feito por estruturas de repetição (for, while). Na recursão, a repetição é obtida através de chamadas de função. A recursão pode levar a código mais limpo para problemas recursivos, mas iteração é geralmente mais eficiente.

2. Recursão é sempre mais lenta que iteração?

Nem sempre. Depende da implementação e da linguagem. Linguagens que otimizam recursão em cauda podem executar recursão com performance similar à iteração. Em linguagens como Python, recursão tem overhead adicional e limite de profundidade, então iteração é mais segura para grandes volumes.

3. O que é recursão em cauda (tail recursion)?

Uma função é tail recursive quando a chamada recursiva é a última operação executada na função. Isso permite que o compilador/interpretador reutilize o quadro da pilha atual, evitando crescimento linear da pilha. Python não otimiza tail recursion, mas outras linguagens como Scheme ou Elixir sim.

4. Como identificar se um problema pode ser resolvido com recursão?

Problemas que podem ser decompostos em subproblemas menores e semelhantes ao original são candidatos naturais à recursão. Exemplos clássicos: travessia de árvores, cálculo de fatorial, Fibonacci, busca binária, algoritmos de ordenação (quicksort, mergesort), e problemas de backtracking.