0Pricing
DSA Interview Prep · Aula

Recursão e o Método da Árvore de Recorrência

Rastreie chamadas recursivas em árvores, aplique o Teorema Mestre e derive complexidades temporais para ordenação por intercalação, fatorial e variantes de Fibonacci.

Recursão e o Método da Árvore de Recorrência é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.

Recursão e a pilha de chamadas

Quando uma função chama a si mesma, cada chamada adiciona um quadro na pilha, acumulando-se até que um caso-base seja alcançado e os quadros sejam desempilhados. Visualizar isso é o primeiro passo para analisar a recursão.

def factorial(n):
    if n == 0:       # base case
        return 1
    return n * factorial(n - 1)  # recursive call

# Call chain: factorial(4)
#   4 * factorial(3)
#     3 * factorial(2)
#       2 * factorial(1)
#         1 * factorial(0) -> 1
# Unwinds: 1, 2, 6, 24
print(factorial(5))  # 120

A árvore de recursão de Fibonacci

Uma árvore de recursão expande cada chamada em suas subchamadas. O Fibonacci ingênuo se divide em duas chamadas a cada vez, formando uma árvore com cerca de 2^n nós — isso resulta em O(2^n). Consulte o código.

call_count = [0]

def fib_naive(n):
    call_count[0] += 1
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

for n in [5, 10, 15, 20]:
    call_count[0] = 0
    result = fib_naive(n)
    print(f'fib({n})={result}, calls={call_count[0]}')
# Calls roughly double each time n increases by 1

Identificando subproblemas repetidos

Nessa árvore, as mesmas chamadas, como fib(3), se repetem em diferentes ramos. Esses subproblemas sobrepostos são o sinal de que se deve usar memoização, que reduz O(2^n) para O(n).

# Memoised: each unique sub-problem computed once
def fib_memo(n, memo={}):
    if n in memo: return memo[n]
    if n <= 1:    return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

call_count2 = [0]
def fib_counted(n, memo={}):
    call_count2[0] += 1
    if n in memo: return memo[n]
    if n <= 1:    return n
    memo[n] = fib_counted(n-1, memo) + fib_counted(n-2, memo)
    return memo[n]

fib_counted(20)
print(f'calls with memo: {call_count2[0]}')  # only 21

Árvore de recursão da ordenação por intercalação

A árvore da ordenação por intercalação tem log n níveis, e cada nível realiza O(n) de trabalho no total — cada elemento é acessado uma vez. Multiplique esses valores para obter O(n log n). Consulte o código.

# Merge sort: at each level, n total elements are merged
# Level 0:  1 merge of n elements    -> n work
# Level 1:  2 merges of n/2 each     -> n work
# Level 2:  4 merges of n/4 each     -> n work
# ...log(n) levels...
# Total: n * log(n)

# Verify with operation counter:
def merge_sort_counted(arr):
    ops = [0]
    def _sort(a):
        if len(a) <= 1: return a
        m = len(a) // 2
        l, r = _sort(a[:m]), _sort(a[m:])
        result, i, j = [], 0, 0
        while i < len(l) and j < len(r):
            ops[0] += 1
            if l[i] <= r[j]: result.append(l[i]); i+=1
            else:             result.append(r[j]); j+=1
        return result + l[i:] + r[j:]
    return _sort(arr), ops[0]

_, c = merge_sort_counted(list(range(64, 0, -1)))
print(f'Merge ops: {c}')  # ~384 ~ 64*log2(64)=384

O Teorema Mestre

O Teorema Mestre resolve T(n) = a*T(n/b) + O(n^d) com três casos. Para a ordenação por intercalação (a=2, b=2, d=1), ele resulta em O(n log n). Memorize os três casos para a prova.

# Merge sort: T(n) = 2*T(n/2) + O(n)
# a=2, b=2, d=1, log_b(a)=log2(2)=1=d  => O(n log n)

# Binary search: T(n) = 1*T(n/2) + O(1)
# a=1, b=2, d=0, log2(1)=0=d  => O(log n)

# Strassen matrix mult: T(n) = 7*T(n/2) + O(n^2)
# a=7, b=2, d=2, log2(7)~2.81 > 2 => O(n^log2(7)) ~ O(n^2.81)

import math
print('log2(7) =', math.log2(7))  # 2.807...

Desenhando árvores de recursão passo a passo

Para desenhar uma árvore de recursão: coloque T(n) no topo, expanda cada chamada, some o trabalho de cada nível e depois multiplique pelo número de níveis. Pratique até isso se tornar automático.

# Factorial: T(n) = T(n-1) + O(1)
# Tree is a chain: n levels, O(1) each -> O(n)

# Fibonacci: T(n) = T(n-1) + T(n-2) + O(1)
# Binary tree of depth n, ~2^n nodes -> O(2^n)

# Merge sort: T(n) = 2*T(n/2) + O(n)
# Log levels, n work each -> O(n log n)

def count_recursive_calls(n, results=[]):
    if n <= 1:
        results.append(n)
        return n
    return count_recursive_calls(n-1, results) + count_recursive_calls(n-2, results)

results = []
count_recursive_calls(8, results)
print(f'fib(8) leaf calls: {len(results)}')

Recursão exponencial: subsets

Gerar todos os subconjuntos resulta em O(2^n) — existem exatamente 2^n deles, portanto não é possível fazer melhor. Cada elemento entra ou não entra, formando uma árvore binária de escolhas. Consulte o código.

def subsets(nums):
    result = []
    def backtrack(start, current):
        result.append(list(current))  # O(n) copy
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    backtrack(0, [])
    return result

nums = [1, 2, 3]
ss = subsets(nums)
print(len(ss))  # 8 = 2^3
print(ss)

Recursão de cauda e otimização

Recursão de cauda ocorre quando a chamada recursiva é a última etapa. Algumas linguagens reutilizam o quadro nesse caso, mas o Python não — portanto, recursões profundas ainda estouram a pilha. Prefira um laço.

# Tail-recursive factorial (accumulator pattern)
def fact_tail(n, acc=1):
    if n == 0:
        return acc
    return fact_tail(n - 1, n * acc)  # tail call

# Python does NOT TCO, so this overflows for large n
# Instead, convert to iterative:
def fact_iter(n):
    acc = 1
    while n > 0:
        acc *= n
        n -= 1
    return acc

print(fact_tail(10))  # 3628800
print(fact_iter(10))  # 3628800

Complexidade espacial da recursão

Cada chamada recursiva mantém um quadro, portanto a recursão usa espaço O(profundidade). A recursão linear é O(n); a DFS em uma árvore balanceada é O(log n). Se você for fundo demais, encontrará um RecursionError.

import sys
print(sys.getrecursionlimit())  # default 1000

# Increase limit for deep problems
sys.setrecursionlimit(10000)

# Track max depth manually
def max_depth_tracker(n, depth=0, max_seen=[0]):
    max_seen[0] = max(max_seen[0], depth)
    if n <= 0:
        return
    max_depth_tracker(n - 1, depth + 1, max_seen)
    return max_seen[0]

print(max_depth_tracker(50))  # 50  => O(n) stack frames

Árvore de recursão da ordenação rápida

A ordenação rápida é O(n log n) com um bom pivô, mas um pivô ruim em uma entrada ordenada faz o algoritmo degradar para O(n^2). Por isso é importante escolher o pivô aleatoriamente. Consulte o código.

import random

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)  # randomised -> O(n log n) expected
    less    = [x for x in arr if x < pivot]
    equal   = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

print(quick_sort([3, 6, 8, 10, 1, 2, 1]))  # sorted

Função de potência: recursão logarítmica

O método ingênuo para x^n exige O(n) multiplicações, mas elevar ao quadrado reduz o trabalho pela metade a cada etapa: x^n = (x^(n/2))^2. Isso resulta em um elegante O(log n) — a redução pela metade em ação. Consulte o código.

def fast_pow(x, n):
    if n == 0: return 1
    if n < 0:  return 1 / fast_pow(x, -n)
    if n % 2 == 0:
        half = fast_pow(x, n // 2)
        return half * half          # O(log n) calls
    return x * fast_pow(x, n - 1)

print(fast_pow(2, 10))   # 1024
print(fast_pow(3, 5))    # 243
# Only log2(10)=3-4 recursive calls for n=10

Verificação rápida

Verificação rápida — mostre o que o método da árvore de recursão ensinou a você. É uma pergunta só; faça com calma. 🌳

Recapitulação da lição

Recapitulação: uma árvore de recursão revela o trabalho total, o Teorema Mestre resolve recorrências de divisão e conquista, e a recursão usa espaço de pilha O(profundidade).

Perguntas Frequentes

A aula “Recursão e o Método da Árvore de Recorrência” é grátis?

Sim — o texto completo de “Recursão e o Método da Árvore de Recorrência” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.

O que vou aprender em “Recursão e o Método da Árvore de Recorrência”?

Rastreie chamadas recursivas em árvores, aplique o Teorema Mestre e derive complexidades temporais para ordenação por intercalação, fatorial e variantes de Fibonacci. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar DSA Interview Prep?

Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.

Quanto tempo leva a aula “Recursão e o Método da Árvore de Recorrência”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de DSA Interview Prep?

Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Notação Big-O do Zero
  2. Analisando Laços e Laços Aninhados
  3. Recursão e o Método da Árvore de Recorrência
  4. Complexidade de Espaço e Compromissos
← Voltar para DSA Interview Prep