Recursão e árvores binárias de busca

Uma função que chama a si mesma resolve um problema grande a partir de versões menores dele. Hoje usamos essa ideia para percorrer estruturas hierárquicas e montar a árvore binária de busca, que encontra um valor entre milhões em poucas comparações.

f(n−1)Recursãocaso base, pilha de chamadas raizÁrvores bináriasnós, folhas, altura e percursos esq < raiz < dirÁrvore binária de buscabuscar, inserir, remover ✓ 6Práticaexercícios com correção automática

Navegação: ← → trocam de etapa · V alterna entre etapas e página única · M sumário · F tela cheia · + − tamanho do texto · dentro do código, Ctrl+Enter executa.

Todo código desta aula pode ser editado e executado aqui mesmo. Altere os exemplos à vontade; o botão ↺ restaura o original. Suas alterações ficam salvas neste navegador; em Progresso você pode baixá-las em um arquivo e continuar em outro computador.

As visualizações mostram os algoritmos passo a passo: altere os dados, use Próximo passo ou Animar. Nos exercícios, o botão ✓ Verificar testa seu código com várias entradas.

Uma função que chama a si mesma

Uma função é recursiva quando resolve um problema chamando a si mesma para uma versão menor do mesmo problema.

Toda recursão correta tem duas partes:

Caso base: uma entrada tão pequena que a resposta é direta, sem nova chamada.
Passo recursivo: reduz o problema e confia que a chamada menor devolve a resposta certa.

O fatorial tem uma definição recursiva natural: 0! = 1! = 1 e n! = n × (n − 1)!.

4! = 4 × 3!3! = 3 × 2!2! = 2 × 1!1! = 1

Pense na recursão como uma delegação: “eu sei resolver o 4 se alguém me der a resposta do 3”.

A pilha de chamadas

Cada chamada ganha um quadro próprio na memória, com suas variáveis. Uma chamada que espera outra fica parada embaixo dela: é uma pilha. A última a entrar é a primeira a terminar.

A pilha cresce até o caso base e depois desmonta: cada quadro recebe o resultado do de cima, faz a sua conta e sai.

Troque a função para soma(lista) na visualização e acompanhe soma([3, 1, 4, 2]) = 3 + soma([1, 4, 2]).

Cada quadro ocupa memória. Com a recursão profunda demais (milhares de chamadas esperando), a pilha estoura: o Python lança RecursionError.

Recursão sobre listas e strings

Uma lista é “o primeiro elemento + o resto da lista”. O resto é uma lista menor: perfeito para o passo recursivo. O caso base costuma ser a lista vazia (ou com um elemento).

Problema	Caso base	Passo
soma	`[]` → 0	`v[0] + soma(v[1:])`
máximo	1 elemento → ele	maior entre `v[0]` e `maximo(v[1:])`
inverter	até 1 letra → ela	`inverte(s[1:]) + s[0]`
palíndromo	até 1 letra → True	pontas iguais e o miolo é palíndromo

v[1:] cria uma cópia da lista a cada chamada, o que deixa a soma O(n²). Para listas grandes, passe um índice (soma(v, i + 1)) em vez de fatiar.

Fibonacci: a árvore de chamadas

Quando a função chama a si mesma duas vezes, as chamadas formam uma árvore. Em fib(n) = fib(n − 1) + fib(n − 2), os mesmos valores são calculados de novo e de novo.

Na visualização, o número ao lado de cada nó é o valor devolvido. Conte quantas vezes aparece f(2).

O número de chamadas cresce quase como 1,6ⁿ: a versão ingênua é exponencial. Para n = 40, são mais de 300 milhões de chamadas.

Memorização: não recalcule

Guardamos cada resultado em um dicionário na primeira vez que ele é calculado. Nas próximas, a resposta sai na hora.

Com o dicionário memo, cada fib(k) é calculado uma única vez: a árvore vira quase uma linha e o custo cai para O(n).

Essa técnica (guardar respostas de subproblemas) é a base da programação dinâmica.

Compare na visualização: mude entre “sem” e “com memorização” mantendo o mesmo n e observe o contador de chamadas.

Busca binária recursiva

A busca binária da aula de complexidade e busca é naturalmente recursiva: procurar no vetor é olhar o meio e procurar em uma das metades.

Caso base 1: o trecho ficou vazio (ini > fim) → -1.
Caso base 2: o meio é o alvo → devolve meio.
Passo: chama a si mesma em uma metade.

Cada chamada reduz o trecho pela metade: a pilha tem cerca de log₂ n quadros (no máximo ⌊log₂ n⌋ + 2, contando a chamada do trecho vazio). Uma única chamada recursiva por nível → O(log n).

Erros comuns: recursão sem fim

Esquecer o caso base: a função nunca para de se chamar.
Passo que não se aproxima do caso base: fatorial(n + 1), ou soma(v) em vez de soma(v[1:]).
Caso base que nunca é alcançado: if n == 0 com n negativo ou diminuindo de 2 em 2 a partir de um ímpar.
Esquecer o return no passo: a chamada calcula o resultado e ele se perde (a função devolve None).

O Python limita a profundidade da pilha (cerca de 1000 quadros) e lança RecursionError antes de a memória acabar.

Peça para a turma prever a saída antes de executar. Depois, corrija adicionando o caso base.

Recursão × iteração

Todo algoritmo recursivo pode ser reescrito com laços (às vezes com uma pilha explícita), e vice-versa. Qual usar?

	Recursão	Iteração
Clareza	natural para estruturas hierárquicas (árvores, pastas) e “dividir para conquistar”	natural para percorrer sequências
Memória	um quadro por chamada pendente	constante
Limite	profundidade máxima (~1000 em Python)	nenhum

Regra prática: se a profundidade pode chegar a milhares (percorrer uma lista longa), prefira o laço. Se é proporcional a log n ou à altura de uma árvore equilibrada, a recursão é ótima.

Recursão em estruturas hierárquicas

Pastas contêm arquivos e outras pastas, que contêm arquivos e outras pastas… A estrutura é definida em termos dela mesma, então a função que a percorre também é.

No exemplo, uma pasta é um dicionário nome → conteúdo, e um arquivo é só o seu tamanho (um int):

caso base: um arquivo → devolve o tamanho;
passo: uma pasta → soma o tamanho de cada item dentro dela.

Organogramas, menus, comentários com respostas, o DOM de uma página HTML e expressões matemáticas têm a mesma forma: são árvores.

Experimente: escreva contar_arquivos(pasta) e maior_arquivo(pasta).

Desafio: Torre de Hanói

Três hastes (A, B, C) e n discos de tamanhos diferentes, todos em A. Leve todos para C, movendo um disco por vez e nunca pondo um disco maior sobre um menor.

Pense recursivamente: para mover n discos de A para C,

mova os n − 1 de cima de A para B (usando C);
mova o maior disco de A para C;
mova os n − 1 de B para C (usando A).

Mostre cada movimento e o total. Para n discos, são 2ⁿ − 1 movimentos.

n = 1 → 1n = 3 → 7n = 10 → 1023

Mostrar uma solução

Árvores: vocabulário

Uma árvore é formada por nós ligados de forma hierárquica: um nó especial no topo (a raiz) e, abaixo de cada nó, seus filhos. Em uma árvore binária, cada nó tem no máximo dois filhos: o da esquerda e o da direita.

Termo	Significado
raiz	o nó sem pai, no topo
folha	nó sem filhos
nó interno	nó com pelo menos um filho
subárvore	um nó e todos os seus descendentes

Termo	Significado
nível (profundidade)	nº de arestas da raiz até o nó (raiz: 0)
altura do nó	nº de arestas do nó até a folha mais distante (folha: 0)
altura da árvore	altura da raiz (árvore vazia: −1)

A definição é recursiva: uma árvore binária é vazia ou é um nó com uma subárvore esquerda e uma direita, que também são árvores binárias.

Nós em Python

Cada nó é um objeto com a chave e duas referências: esq e dir. None representa a subárvore vazia.

Como a árvore é recursiva, as funções sobre ela seguem sempre o mesmo molde:

caso base: no is None (árvore vazia);
passo: combine o nó atual com o resultado das chamadas em no.esq e no.dir.

tamanho = 1 + tam(esq) + tam(dir)altura = 1 + max(alt(esq), alt(dir))

Cada nó é visitado uma vez: essas funções são O(n).

Percursos: pré-ordem, em ordem e pós-ordem

Percorrer é visitar todos os nós. Nos três percursos em profundidade, a recursão desce pela esquerda e depois pela direita; muda apenas quando o nó atual é visitado.

Percurso	Ordem	Uso típico
pré-ordem	raiz, esq, dir	copiar a árvore, imprimir hierarquias
em ordem	esq, raiz, dir	listar uma ABB em ordem crescente
pós-ordem	esq, dir, raiz	apagar a árvore, somar tamanhos de pastas

Percurso em nível (em largura)

Visita os nós nível por nível, da esquerda para a direita. Não é recursivo: usa uma fila para lembrar quem ainda falta visitar.

Coloque a raiz na fila.
Enquanto a fila não estiver vazia: tire o nó da frente, visite-o e coloque seus filhos no fim.

Como a fila é FIFO (o primeiro que entra é o primeiro que sai), os nós de um nível saem antes dos do nível seguinte.

collections.deque tira da frente em O(1); list.pop(0) seria O(n).

Na aula de grafos, esse mesmo algoritmo vira a busca em largura (BFS).

Árvore binária de busca (ABB)

Em uma ABB, para todo nó: as chaves da subárvore esquerda são menores que a dele, e as da direita são maiores. É a busca binária transformada em estrutura.

Para buscar, compare com a raiz e desça para um lado só: cada comparação descarta uma subárvore inteira.

Para inserir, faça a mesma descida até encontrar um filho vazio (None): o novo nó entra ali, sempre como folha.

Experimente: clique em 1 a 7 em ordem e depois em 7 aleatórios. Compare a altura. Busque o maior valor nos dois casos e conte as comparações.

Busca e inserção

A inserção recursiva devolve a raiz da subárvore (possivelmente nova). Assim, no.esq = inserir(no.esq, chave) liga o novo nó no lugar certo.

A busca pode ser recursiva ou, como aqui, um laço que desce a árvore. Em ambos os casos, o caminho vai da raiz até, no máximo, uma folha: O(h), sendo h a altura.

Nesta aula a ABB não guarda chaves repetidas. Outra opção comum é mandar os iguais sempre para a direita, ou guardar um contador no nó.

Mínimo, máximo e ordem crescente

O menor valor está no nó mais à esquerda: desça por esq até não dar mais. O maior, no mais à direita.

O percurso em ordem visita a subárvore esquerda (menores), a raiz e a direita (maiores): sai tudo ordenado.

Inserir n valores em uma ABB e percorrê-la em ordem é um algoritmo de ordenação (tree sort).

Remoção: três casos

O nó removido tem…	O que fazer
nenhum filho (folha)	simplesmente desligá-lo do pai
um filho	o filho sobe e ocupa o lugar dele
dois filhos	copiar para ele o sucessor (menor chave da subárvore direita) e remover o sucessor, que tem no máximo um filho

Por que o sucessor serve? Ele é maior que tudo à esquerda e menor que todo o resto da direita: a propriedade da ABB continua valendo. (O antecessor, maior da esquerda, também funcionaria.)

class No:
    def __init__(self, chave):
        self.chave = chave
        self.esq = None
        self.dir = None

def inserir(no, chave):
    if no is None:
        return No(chave)
    if chave < no.chave:
        no.esq = inserir(no.esq, chave)
    elif chave > no.chave:
        no.dir = inserir(no.dir, chave)
    return no

def remover(no, chave):
    if no is None:                    # não estava na árvore
        return None
    if chave < no.chave:
        no.esq = remover(no.esq, chave)
    elif chave > no.chave:
        no.dir = remover(no.dir, chave)
    else:
        if no.esq is None:            # 0 ou 1 filho
            return no.dir
        if no.dir is None:
            return no.esq
        s = no.dir                    # 2 filhos: acha o sucessor
        while s.esq is not None:
            s = s.esq
        no.chave = s.chave
        no.dir = remover(no.dir, s.chave)
    return no

def em_ordem(no):
    return em_ordem(no.esq) + [no.chave] + em_ordem(no.dir) if no else []

raiz = None
for k in [50, 30, 70, 20, 40, 60, 80, 65, 75]:
    raiz = inserir(raiz, k)
for k in [20, 60, 70, 50]:
    raiz = remover(raiz, k)
    print("sem", k, "->", em_ordem(raiz), "| raiz:", raiz.chave)

O custo depende da altura

Buscar, inserir e remover descem um caminho da raiz: custam O(h). Tudo depende da forma da árvore.

Forma	Altura com n nós	Busca
equilibrada (cheia)	≈ log₂ n	O(log n)
inserções aleatórias	proporcional a log n (em média, abaixo de 3 · log₂ n)	O(log n) em média
degenerada (inserção em ordem)	n − 1	O(n), como uma lista

Dados que chegam ordenados (datas, matrículas, IDs crescentes) são comuns na vida real e geram justamente o pior caso. As árvores AVL e rubro-negras, da próxima aula, se reequilibram sozinhas e garantem altura O(log n).

import random, math

class No:
    def __init__(self, chave):
        self.chave = chave
        self.esq = None
        self.dir = None

def inserir(raiz, chave):             # versão com laço (sem limite de recursão)
    novo = No(chave)
    if raiz is None:
        return novo
    no = raiz
    while True:
        if chave < no.chave:
            if no.esq is None:
                no.esq = novo
                return raiz
            no = no.esq
        else:
            if no.dir is None:
                no.dir = novo
                return raiz
            no = no.dir

def altura(raiz):                     # conta os níveis, sem recursão
    nivel, h = [raiz], -1
    while nivel:
        h += 1
        nivel = [f for no in nivel for f in (no.esq, no.dir) if f]
    return h

n = 500
aleatoria = None
for k in random.sample(range(n), n):
    aleatoria = inserir(aleatoria, k)
ordenada = None
for k in range(n):
    ordenada = inserir(ordenada, k)

print("n =", n)
print("altura com inserção aleatória:", altura(aleatoria))
print("altura com inserção em ordem: ", altura(ordenada))
print("menor altura possível:        ", math.ceil(math.log2(n + 1)) - 1)

Perguntas sobre árvores

Desenhe a árvore no caderno quando precisar. Responda e só então clique.

Qual será a saída?

Leia o código, escreva sua resposta e só então clique. Errou? Copie o código para o laboratório e execute.

Prática 1: recursão

Escreva sua solução no editor. ▶ Executar roda com a entrada que você quiser; ✓ Verificar roda os testes automáticos e mostra o que falta. Resolva com funções recursivas, sem laços.

1. Soma dos dígitos básico

Leia um inteiro n ≥ 0 e mostre a soma dos seus dígitos usando uma função recursiva. Dica: o último dígito é n % 10 e o resto do número é n // 10; um número de um dígito é o caso base.

Entrada	Saída esperada
1234	Soma dos dígitos: 10

Mostrar uma solução

2. Potência rápida médio

Leia b e (inteiros, e ≥ 0) e calcule bᵉ sem ** nem pow. A versão ingênua (b * pot(b, e − 1)) faz e + 1 chamadas. Faça em O(log e): calcule m = pot(b, e // 2) uma única vez; o resultado é m * m, vezes b se e for ímpar. Mostre também quantas vezes a função foi chamada (contando a primeira).

Entrada	Saída esperada
2 10	Resultado: 1024 Chamadas: 5

Mostrar uma solução

Prática 2: árvores

Nos dois exercícios, a primeira linha traz chaves inteiras, que são inseridas nessa ordem em uma ABB (repetidas são ignoradas). O código inicial já monta a árvore.

3. Nós, altura e folhas básico

Escreva as funções recursivas tamanho, altura e folhas e mostre os três valores. A altura de uma folha é 0.

Entrada	Saída esperada
50 30 70 20 40 60 80	Nós: 7 Altura: 2 Folhas: 4

Mostrar uma solução

4. O k-ésimo menor médio

A segunda linha traz um inteiro k. Mostre a k-ésima menor chave da árvore (k = 1 é a menor) ou k inválido se não existir. Use o percurso em ordem; não use sort() nem sorted().

Entrada	Saída esperada
50 30 70 20 40 60 80 3	3º menor: 40

Mostrar uma solução

Prática 3: propriedades da árvore

5. Nível de cada chave médio

Leia as chaves de uma ABB (inseridas na ordem dada) e mostre, em ordem crescente, uma linha chave: nível N para cada nó. A raiz está no nível 0. Dica: passe o nível como parâmetro na recursão.

Entrada	Saída esperada
50 30 70 20 40	20: nível 2 30: nível 1 40: nível 2 50: nível 0 70: nível 1

Mostrar uma solução

6. É uma ABB? desafio

A árvore vem em nível, com - para filho vazio (o código inicial já a monta). Verifique se é uma ABB com chaves distintas: todas as chaves à esquerda de um nó menores que ele e todas à direita maiores. Mostre Resultado: ABB válida ou Resultado: não é ABB.

Cuidado: comparar cada nó só com os filhos não basta. Em 50 30 70 20 60, o 60 é filho direito do 30 (ok), mas está à esquerda do 50. Dica: passe para a recursão o intervalo (mínimo, máximo) permitido.

Mostrar uma solução

from collections import deque

class No:
    def __init__(self, chave):
        self.chave = chave
        self.esq = None
        self.dir = None

def montar(tokens):
    if not tokens or tokens[0] == "-":
        return None
    raiz = No(int(tokens[0]))
    fila = deque([raiz])
    i = 1
    while fila and i < len(tokens):
        no = fila.popleft()
        for lado in ("esq", "dir"):
            if i < len(tokens) and tokens[i] != "-":
                filho = No(int(tokens[i]))
                setattr(no, lado, filho)
                fila.append(filho)
            i += 1
    return raiz

raiz = montar(input("Árvore em nível: ").split())

def eh_abb(no, minimo, maximo):
    if no is None:
        return True
    if (minimo is not None and no.chave <= minimo) or (maximo is not None and no.chave >= maximo):
        return False
    # à esquerda, tudo menor que no.chave; à direita, tudo maior
    return eh_abb(no.esq, minimo, no.chave) and eh_abb(no.dir, no.chave, maximo)

if eh_abb(raiz, None, None):
    print("Resultado: ABB válida")
else:
    print("Resultado: não é ABB")

Laboratório livre

Espaço para testar ideias durante a aula. Sugestões: escreva contar_arquivos(pasta) para o exemplo das pastas; imprima uma ABB “deitada” (direita em cima, com recuo pelo nível); implemente a busca e a inserção da ABB sem recursão; conte quantas chamadas faz fib(25) com e sem memorização.