Recursão e Estruturas de Dados Avançadas: pilhas, filas e árvores

Recursão e estruturas de dados avançadas são o ponto em que a programação começa a se parecer com engenharia. Pilhas, filas e árvores não são abstrações acadêmicas — estão presentes no histórico de navegação do seu browser, na fila de impressão do seu sistema operacional e na estrutura de pastas do seu computador. Entendê-las torna você capaz de resolver problemas que listas e dicionários simples não conseguem modelar bem.

Recursão

Uma função recursiva é aquela que chama a si mesma. Todo problema recursivo tem dois componentes obrigatórios:

• Caso base — a condição que encerra as chamadas
• Caso recursivo — a chamada que reduz o problema

Sem caso base, a recursão nunca termina e o Python lança RecursionError.

Exemplo clássico: fatorial

def fatorial(n):
    """
    fatorial(5) = 5 * 4 * 3 * 2 * 1 = 120
    Caso base: fatorial(0) = 1
    """
    if n == 0:          # caso base
        return 1
    return n * fatorial(n - 1)   # caso recursivo


print(fatorial(5))   # 120
print(fatorial(10))  # 3628800

Visualizando as chamadas:

fatorial(5)
  └─ 5 * fatorial(4)
           └─ 4 * fatorial(3)
                    └─ 3 * fatorial(2)
                             └─ 2 * fatorial(1)
                                      └─ 1 * fatorial(0)
                                                └─ 1  ← caso base

Sequência de Fibonacci

def fibonacci(n):
    """Retorna o n-ésimo número de Fibonacci."""
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)


for i in range(10):
    print(fibonacci(i), end=" ")
# 0 1 1 2 3 5 8 13 21 34

Esta implementação é correta, mas ineficiente — O(2ⁿ). O mesmo valor é calculado várias vezes. A solução é o memoization:

from functools import lru_cache

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


print(fibonacci(50))   # 12586269025 — instantâneo
print(fibonacci(100))  # 354224848179261915075

O decorator @lru_cache armazena resultados já calculados, reduzindo a complexidade para O(n).

Limite de recursão

O Python limita a profundidade de recursão para evitar estouro de pilha:

import sys
print(sys.getrecursionlimit())  # 1000 por padrão

sys.setrecursionlimit(5000)     # aumentar se necessário, com cautela

Para problemas com profundidade muito grande, prefira a versão iterativa.

Pilhas (Stacks)

Uma pilha segue o princípio LIFO — Last In, First Out. O último elemento inserido é o primeiro a sair. Pense em uma pilha de pratos.

Inserir (push): [ ] → [A] → [A,B] → [A,B,C]
Remover (pop):  [A,B,C] → [A,B] → [A] → [ ]

Em Python, listas já implementam pilhas eficientemente:

pilha = []

# push — adiciona no topo
pilha.append("página inicial")
pilha.append("produtos")
pilha.append("detalhes do produto")

print(pilha)
# ['página inicial', 'produtos', 'detalhes do produto']

# pop — remove do topo
pagina_atual = pilha.pop()
print(pagina_atual)  # detalhes do produto
print(pilha)         # ['página inicial', 'produtos']

Implementando uma classe Pilha

class Pilha:
    def __init__(self):
        self._dados = []

    def push(self, item):
        self._dados.append(item)

    def pop(self):
        if self.vazia():
            raise IndexError("Pop em pilha vazia.")
        return self._dados.pop()

    def topo(self):
        if self.vazia():
            raise IndexError("Pilha vazia.")
        return self._dados[-1]

    def vazia(self):
        return len(self._dados) == 0

    def tamanho(self):
        return len(self._dados)

    def __repr__(self):
        return f"Pilha({self._dados})"


# Uso: verificador de parênteses balanceados
def parenteses_balanceados(expressao):
    """Verifica se os parênteses, colchetes e chaves estão balanceados."""
    pilha = Pilha()
    abre = "({["
    fecha = ")}]"
    pares = {")": "(", "}": "{", "]": "["}

    for char in expressao:
        if char in abre:
            pilha.push(char)
        elif char in fecha:
            if pilha.vazia() or pilha.pop() != pares[char]:
                return False

    return pilha.vazia()


print(parenteses_balanceados("(a + b) * [c - d]"))   # True
print(parenteses_balanceados("(a + b] * [c - d)"))   # False
print(parenteses_balanceados("{[()]}"))               # True
print(parenteses_balanceados("{[(])}"))               # False

Filas (Queues)

Uma fila segue o princípio FIFO — First In, First Out. O primeiro a entrar é o primeiro a sair. Pense em uma fila de banco.

Listas não são ideais para filas — remover do início (pop(0)) é O(n). Use collections.deque:

from collections import deque

fila = deque()

# enqueue — adiciona no final
fila.append("Cliente A")
fila.append("Cliente B")
fila.append("Cliente C")

print(fila)  # deque(['Cliente A', 'Cliente B', 'Cliente C'])

# dequeue — remove do início — O(1)
proximo = fila.popleft()
print(proximo)  # Cliente A
print(fila)     # deque(['Cliente B', 'Cliente C'])

Fila de prioridade com heapq

Quando a ordem de saída depende de uma prioridade e não da chegada:

import heapq

fila_prioridade = []

# (prioridade, tarefa) — menor número = maior prioridade
heapq.heappush(fila_prioridade, (3, "Enviar relatório"))
heapq.heappush(fila_prioridade, (1, "Corrigir bug crítico"))
heapq.heappush(fila_prioridade, (2, "Revisar pull request"))
heapq.heappush(fila_prioridade, (1, "Atender chamado urgente"))

while fila_prioridade:
    prioridade, tarefa = heapq.heappop(fila_prioridade)
    print(f"[P{prioridade}] {tarefa}")

# [P1] Atender chamado urgente
# [P1] Corrigir bug crítico
# [P2] Revisar pull request
# [P3] Enviar relatório

Olhe a ordem das duas tarefas de prioridade 1. O chamado urgente foi inserido por último e saiu primeiro — não por alguma regra de desempate do heapq, mas porque, empatada a prioridade, a comparação passa para o segundo elemento da tupla, e "Atender…" vem antes de "Corrigir…" no alfabeto. O heapq não é estável e não preserva ordem de chegada.

Isso é mais que uma curiosidade, porque quebra assim que a tarefa deixa de ser texto:

heapq.heappush(fila, (1, {"id": 1}))
heapq.heappush(fila, (1, {"id": 2}))
# TypeError: '<' not supported between instances of 'dict' and 'dict'

Com dicionários, objetos ou qualquer coisa sem ordem definida, o empate de prioridade derruba o programa — e só quando dois itens empatam, o que faz o defeito escapar dos testes. A solução canônica é acrescentar um contador monotônico como segundo elemento, que nunca empata e ainda devolve a ordem de chegada de brinde:

import itertools

contador = itertools.count()
fila = []

heapq.heappush(fila, (1, next(contador), {"id": "primeiro"}))
heapq.heappush(fila, (1, next(contador), {"id": "segundo"}))
# desempata pela chegada, e o terceiro elemento nunca é comparado

Árvores

Uma árvore é uma estrutura hierárquica composta por nós. Cada nó tem um valor e pode ter nós filhos. O nó sem pai é chamado de raiz.

        10          ← raiz
       /  \
      5    15       ← filhos da raiz
     / \     \
    3   7     20    ← folhas

Árvore Binária de Busca (BST)

Na BST, para cada nó: todos os valores à esquerda são menores, todos à direita são maiores.

class No:
    def __init__(self, valor):
        self.valor = valor
        self.esquerda = None
        self.direita = None


class ArvoreBinariaBusca:
    def __init__(self):
        self.raiz = None

    def inserir(self, valor):
        self.raiz = self._inserir(self.raiz, valor)

    def _inserir(self, no, valor):
        if no is None:
            return No(valor)
        if valor < no.valor:
            no.esquerda = self._inserir(no.esquerda, valor)
        elif valor > no.valor:
            no.direita = self._inserir(no.direita, valor)
        return no

    def buscar(self, valor):
        return self._buscar(self.raiz, valor)

    def _buscar(self, no, valor):
        if no is None:
            return False
        if valor == no.valor:
            return True
        if valor < no.valor:
            return self._buscar(no.esquerda, valor)
        return self._buscar(no.direita, valor)

    def em_ordem(self):
        """Percurso em ordem — retorna valores em ordem crescente."""
        resultado = []
        self._em_ordem(self.raiz, resultado)
        return resultado

    def _em_ordem(self, no, resultado):
        if no:
            self._em_ordem(no.esquerda, resultado)
            resultado.append(no.valor)
            self._em_ordem(no.direita, resultado)


arvore = ArvoreBinariaBusca()
for valor in [10, 5, 15, 3, 7, 20]:
    arvore.inserir(valor)

print(arvore.em_ordem())    # [3, 5, 7, 10, 15, 20]
print(arvore.buscar(7))     # True
print(arvore.buscar(99))    # False

O que esta árvore não faz: balancear

A promessa de busca em O(log n) vale para uma árvore balanceada, e esta implementação não balanceia nada — ela apenas insere onde a comparação mandar. Enquanto os valores chegam embaralhados, o resultado é aceitável; quando chegam ordenados, cada novo valor é sempre maior que o anterior e vai sempre para a direita. A árvore vira uma lista ligada com passos extras, e a busca volta a ser O(n).

Medindo com mil valores na 3.14:

1000 valores embaralhados -> altura 21   (log2(1000) é cerca de 10)
1000 valores ordenados    -> RecursionError: maximum recursion depth exceeded

O caso ordenado não fica apenas lento: ele quebra. Como a inserção é recursiva e desce um nível por elemento, mil inserções em ordem crescente significam mil chamadas aninhadas, e o limite padrão de recursão é exatamente 1000. E ordenado é o caso mais comum que existe em dado real — registros lidos de um banco por identificador, eventos por data, linhas de um arquivo já classificado. É a entrada mais provável, e é a que derruba.

Escrever uma árvore que se reequilibra sozinha, como AVL ou rubro-negra, é assunto de outro nível e raramente necessário: para busca por chave, o dicionário do Python já entrega tempo praticamente constante, com muito menos código. A BST vale como exercício de estrutura e para os casos em que se precisa percorrer em ordem ou consultar faixas — e, mesmo aí, uma lista ordenada com bisect costuma resolver melhor. Implementá-la ensina; usá-la em produção exige saber o que ela não garante.

Exemplo Completo: Avaliador de Expressões

Usando pilha para avaliar expressões matemáticas em notação pós-fixada (RPN — Reverse Polish Notation):

def avaliar_rpn(expressao):
    """
    Avalia expressão em notação pós-fixada.
    Exemplo: "3 4 + 2 *" = (3 + 4) * 2 = 14
    """
    pilha = []
    operadores = {
        "+": lambda a, b: a + b,
        "-": lambda a, b: a - b,
        "*": lambda a, b: a * b,
        "/": lambda a, b: a / b,
    }

    for token in expressao.split():
        if token in operadores:
            b = pilha.pop()
            a = pilha.pop()
            resultado = operadores[token](a, b)
            pilha.append(resultado)
        else:
            pilha.append(float(token))

    if len(pilha) != 1:
        raise ValueError(f"expressão malformada: sobraram {len(pilha)} valores")
    return pilha.pop()


print(avaliar_rpn("3 4 +"))         # 7.0  → 3 + 4
print(avaliar_rpn("3 4 + 2 *"))     # 14.0 → (3 + 4) * 2
print(avaliar_rpn("5 1 2 + 4 * + 3 -"))  # 14.0 → 5 + ((1+2)*4) - 3

Repare na guarda antes do return. A versão natural de escrever essa função termina com return pilha[0], e é ela que aparece na maioria dos materiais — mas devolve um número plausível para entrada malformada, em vez de recusar:

avaliar_rpn("3 4")       # 3.0  — faltou o operador, e ninguém avisa
avaliar_rpn("1 2 3 +")   # 1.0  — sobrou valor na pilha, e ninguém avisa

Nos dois casos a pilha terminou com mais de um elemento, o que é a definição de expressão incompleta, e o pilha[0] devolveu o primeiro valor que sobrou como se fosse o resultado. Numa calculadora de brinquedo isso é um incômodo; num interpretador que recebe entrada de fora, é um valor errado circulando pelo sistema sem sinal nenhum. Conferir que restou exatamente um elemento é a única linha que separa um avaliador de um gerador de resultados aleatórios — e pilha.pop() comunica melhor a intenção que pilha[0], porque deixa explícito que aquele é o último valor, não o primeiro.

As três estruturas deste artigo resolvem perguntas diferentes, e a escolha entre elas é quase sempre ditada pela ponta em que se mexe. Pilha atende quem sempre volta ao último item, e em Python a lista já faz isso bem, com append e pop. Fila atende quem atende por ordem de chegada, e aí a lista é a escolha errada, porque remover do início custa O(n) — o deque existe exatamente para isso. Fila de prioridade é o heapq, com a ressalva de que ele não é estável e, empatada a prioridade, compara o próximo elemento da tupla: com dicionários ou objetos, o empate levanta TypeError, e a correção é um contador monotônico no meio.

Recursão e árvore andam juntas porque uma é a forma natural de percorrer a outra, e as duas trazem o mesmo aviso. Toda recursão consome a pilha de chamadas, cujo limite padrão é mil, e é por isso que a árvore binária de busca deste artigo — que insere recursivamente e não reequilibra nada — não apenas fica lenta com dados ordenados: ela levanta RecursionError com mil valores em ordem crescente, que é a forma mais comum de dado chegar do mundo real. Vale implementá-la para entender como uma hierarquia se percorre; para buscar por chave em produção, o dicionário resolve melhor, com menos código e sem pré-condição que possa ser violada em silêncio.

Fontes e leituras recomendadas

• collections.deque — https://docs.python.org/3/library/collections.html#collections.deque
• heapq — filas de prioridade — https://docs.python.org/3/library/heapq.html
• functools.lru_cache — https://docs.python.org/3/library/functools.html#functools.lru_cache
• sys.setrecursionlimit — https://docs.python.org/3/library/sys.html#sys.setrecursionlimit
• CORMEN, Thomas H. et al. Introduction to Algorithms. 4. ed. MIT Press, 2022. Cap. 10 e 12 — pilhas, filas e árvores binárias de busca.
• GOODRICH, Michael T. et al. Data Structures and Algorithms in Python. Wiley, 2013. Cap. 6, 7 e 8 — implementações completas em Python.
• BHARGAVA, Aditya Y. Grokking Algorithms. Manning, 2016. Cap. 3 — recursão explicada de forma visual e acessível.

Exercícios

Exercício 1

Um serviço indexa registros numa árvore binária de busca como a deste artigo. Nos testes, com dados de exemplo embaralhados, tudo funciona. Ao subir para produção, a carga inicial lê os registros do banco ordenados por identificador e o serviço morre com RecursionError antes de terminar a importação. Explique a ligação entre a ordem dos dados e o erro, e diga por que o teste não pegou.

Exercício 2

Uma fila de prioridade guarda tarefas como heapq.heappush(fila, (prioridade, tarefa)), em que tarefa é um dicionário. Funcionou por semanas e um dia levantou TypeError. O time observa que o erro só ocorre em horários de pico. Explique a relação com o pico e corrija.

Exercício 3

Uma função recursiva calcula o tamanho total de uma árvore de pastas somando o tamanho dos arquivos de cada nível. Funciona no computador de todos os desenvolvedores e falha num servidor específico, com RecursionError. A estrutura de pastas é a mesma nos dois lugares. Levante as hipóteses e diga como resolver sem depender de qual delas é a verdadeira.

Exercício 4

Um avaliador de expressões em notação pós-fixada termina com return pilha[0]. Os testes passam. Em produção, para certas entradas vindas de um formulário, ele devolve números que não correspondem à conta pedida — sem erro nenhum. Mostre duas entradas que produzem resultado errado calado e explique a correção.

Exercício 5

Explique por que um verificador de parênteses balanceados precisa de uma pilha e não pode ser resolvido apenas contando aberturas e fechamentos. Em seguida, relacione esse fato com a razão de toda recursão usar internamente uma pilha.