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

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

Á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

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))

    return pilha[0]


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

Resumo

• Recursão resolve problemas dividindo-os em subproblemas menores — sempre exige caso base
• @lru_cache adiciona memoization automaticamente, tornando recursões repetitivas eficientes
• Pilhas seguem LIFO — list.append() e list.pop() são suficientes em Python
• Filas seguem FIFO — use collections.deque com append() e popleft() para eficiência O(1)
• Filas de prioridade são implementadas com heapq — menor valor sai primeiro
• Árvores representam hierarquias — BST garante busca em O(log n) para árvores balanceadas
• Pilhas e recursão são naturalmente complementares — toda recursão usa a pilha de chamadas internamente

Referências e Leituras Complementares

• 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.

Prof. Ricardo Matos — Dominando o Python em 1 Ano · Artigo 12 de 52

✅ Módulo 2 Concluído — Estruturas de Dados e Algoritmos

Plano Completo da Série — Estado Atual