Recursão Explicada: Quando Usar e Quando Evitar

Uma função que chama a si mesma tem uma profundidade máxima, e ela é menor do que a maioria imagina: 1.000 chamadas no CPython por padrão, algo entre 10.000 e 15.000 no Node e nos motores de navegador, dependendo de quanto cada frame ocupa. Passar desse limite não deixa o programa mais lento. Ele trava. O Python lança RecursionError: maximum recursion depth exceeded; o JavaScript lança RangeError: Maximum call stack size exceeded.

Os dois erros têm a mesma causa. Entenda essa causa e você sabe quando a recursão é a ferramenta certa e quando ela se torna um risco.

O que uma função recursiva realmente faz com a pilha de chamadas

Cada chamada de função coloca um frame na pilha: os argumentos, as variáveis locais, o endereço de retorno. Uma chamada normal retorna e seu frame é removido. Uma chamada recursiva ainda não pode retornar, porque está esperando a chamada que acabou de fazer, então cada frame permanece na pilha até que o de baixo termine.

1
2
3
4

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

factorial(4) monta quatro frames na pilha antes que qualquer um deles produza um valor:

1
2
3
4

factorial(4) -> 4 * factorial(3)
                     factorial(3) -> 3 * factorial(2)
                                          factorial(2) -> 2 * factorial(1)
                                                               factorial(1) -> 1   # caso base, a pilha para de crescer

Só quando factorial(1) retorna 1 a pilha se desenrola: 2 * 1, depois 3 * 2, depois 4 * 6, resultado 24.

Duas partes fazem isso funcionar. O caso base (n <= 1) interrompe a recursão. O caso recursivo chama a função de novo com uma entrada que se aproxima do caso base. Remova qualquer um dos dois e a função nunca mais para de se chamar: no Python você chega ao RecursionError em menos de mil chamadas; numa linguagem sem limite, o processo morre por stack overflow.

Quando a recursão é a ferramenta certa: dados aninhados

A recursão se justifica quando os dados estão aninhados a uma profundidade que você não conhece de antemão: uma árvore, um sistema de arquivos, um JSON aninhado sem limite fixo. Um loop sobre esse tipo de dado precisa de uma pilha controlada manualmente. A recursão dá uma de graça, porque a pilha de chamadas é a pilha de que você precisava.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

flatten([1, [2, 3, [4, [5, 6]], 7], 8])
# [1, 2, 3, 4, 5, 6, 7, 8]

Cada chamada a flatten cuida de um nível. Quando encontra uma lista aninhada, passa essa lista para uma nova chamada, e a pilha lembra onde retomar na lista externa quando a interna terminar. A versão iterativa teria que controlar essa posição por conta própria.

Percorrer uma árvore de diretórios segue a mesma lógica:

1
2
3
4
5
6

from pathlib import Path

def total_size(path: Path) -> int:
    if path.is_file():
        return path.stat().st_size
    return sum(total_size(child) for child in path.iterdir())

total_size não se importa se um diretório tem um nível de profundidade ou dez. Cada chamada cuida do seu próprio path.

Quando a recursão é a ferramenta errada: entrada plana e longa

Somar uma lista plana é o caso oposto. Não há aninhamento, então a recursão não traz vantagem nenhuma, só risco de pilha.

1
2
3
4

def sum_recursive(nums):
    if not nums:
        return 0
    return nums[0] + sum_recursive(nums[1:])

Funciona com entradas pequenas e falha com entradas reais:

1
2
3
4

>>> sum_recursive(list(range(2000)))
Traceback (most recent call last):
  ...
RecursionError: maximum recursion depth exceeded

Dois mil itens, um frame por item, o dobro do limite padrão. A versão com loop usa um único frame, independentemente do tamanho da lista:

1
2
3
4
5

def sum_iterative(nums):
    total = 0
    for n in nums:
        total += n
    return total

sum_iterative(list(range(1_000_000))) retorna instantaneamente. Em termos de notação Big O, as duas versões são O(n) em tempo, mas a recursiva também custa O(n) em espaço de pilha, e esse espaço é limitado a cerca de mil frames.

A tail-call optimization resolve a recursão profunda em Python ou JavaScript?

Não. Em sum_recursive, a última coisa que acontece é a soma, não a chamada recursiva, então cada frame precisa continuar vivo para receber um resultado e somá-lo. É possível reescrevê-la para que a chamada recursiva seja a última operação, levando o total acumulado como argumento:

1
2
3
4

def sum_tail(nums, acc=0):
    if not nums:
        return acc
    return sum_tail(nums[1:], acc + nums[0])

Numa linguagem com tail-call optimization, o compilador percebe que nada do frame de quem chamou é necessário depois da chamada, e reutiliza esse frame em vez de empilhar um novo. A recursão se torna um loop por debaixo dos panos.

O CPython não faz isso, por decisão de design: os desenvolvedores principais rejeitaram a ideia porque tornaria os tracebacks mais difíceis de ler. sum_tail ainda bate no limite numa lista de 2.000 itens. A especificação ES2015 do JavaScript inclui proper tail calls, mas V8 (Chrome, Node.js) e SpiderMonkey (Firefox) nunca as implementaram; só o JavaScriptCore, motor do Safari, faz isso.

Então a regra é a mesma nas duas linguagens. Se o tamanho da entrada decide até onde a recursão vai, não conte com o motor para salvar você. Converta para um loop, ou limite a profundidade.

Como a memoization corrige a recursão lenta

Algumas funções recursivas nunca chegam perto do limite de profundidade. O problema delas é calcular a mesma coisa repetidas vezes. O Fibonacci recursivo ingênuo é o caso clássico:

1
2
3
4

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

fib(5) chama fib(4) e fib(3), e fib(4) chama fib(3) de novo. Essa duplicação se acumula em cada nível, então o número de chamadas cresce exponencialmente com n (por um fator de cerca de 1,6 a cada passo, geralmente escrito como o limite superior O(2^n)). No CPython, fib(30) já leva cerca de um décimo de segundo e fib(40) mais de dez segundos.

A correção deixa a recursão intacta e armazena os resultados em cache, para que cada entrada distinta seja calculada apenas uma vez:

1
2
3
4
5
6
7

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

lru_cache é um decorator. Ele envolve fib_memo, e quando um argumento se repete, retorna o resultado guardado em vez de executar o corpo de novo. fib_memo(40) retorna instantaneamente.

A profundidade não muda: fib_memo(40) ainda precisa de cerca de 40 frames de pilha. O que muda é o número de chamadas, que passa de exponencial para linear. Você paga O(n) de memória pelo cache e ganha O(n) de tempo em vez de exponencial.

Recursão ou iteração: qual usar

Um caso merece mais que uma linha de tabela. Se a profundidade da recursão é controlada por uma entrada em que você não confia, isso é um vetor de negação de serviço. Um parser recursivo que desce um nível por colchete aninhado num texto fornecido pelo usuário pode ser derrubado por qualquer um que envie alguns milhares de caracteres [. Limite a profundidade explicitamente, ou não use recursão.

Como converter uma função recursiva em um loop

O substituto direto da recursão sobre uma árvore é uma pilha explícita: uma list em que você faz push e pop manualmente, controlada por um loop while. Veja flatten reescrita assim:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def flatten_iterative(nested):
    result = []
    stack = [iter(nested)]
    while stack:
        for item in stack[-1]:
            if isinstance(item, list):
                stack.append(iter(item))
                break
            result.append(item)
        else:
            stack.pop()
    return result

Ela produz o mesmo resultado com um único frame de pilha, não importa quão profunda seja a entrada. O custo é o controle que fica visível: a pilha de iteradores é exatamente o que a pilha de chamadas rastreava para você.

Na próxima vez que escrever uma função recursiva, pergunte-se até onde ela pode chegar. Se a resposta for pequena e conhecida (um arquivo de configuração, uma árvore de componentes de interface, uma árvore de parsing da sua própria gramática), mantenha a recursão. Se a resposta for “o que a entrada disser”, escreva o loop.

Artigos relacionados

• Notação Big O Explicada com Exemplos de Código
• Git Bisect: Como Encontrar o Commit que Quebrou seu Código