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 Coding 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 Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding 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)) # 120A á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 1Identificando 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)=384O 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)) # 3628800Complexidade 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])) # sortedFunçã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=10Verificaçã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 Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding 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 Coding 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 Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding 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 Coding Interview Prep?
Sim. Cada aula de Coding 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
- Notação Big-O do Zero
- Analisando Laços e Laços Aninhados
- Recursão e o Método da Árvore de Recorrência
- Complexidade de Espaço e Compromissos