Algoritmos e Estrutura de Dados · FGV · 2026 | Questão sqc-fg129163

Otimização de Algoritmo Recursivo: Fibonacci

Gabarito: letra A. A técnica de memoization consiste em armazenar os resultados de chamadas de função anteriores e reutilizá-los quando os mesmos argumentos são passados novamente, eliminando o recálculo redundante. No caso do Fibonacci recursivo ingênuo, para n=45, a explosão de chamadas repetidas (complexidade exponencial) é resolvida com memoization, mantendo a estrutura recursiva.

O problema descrito é clássico: a função Fibonacci recursiva sem otimização recalcula os mesmos subproblemas inúmeras vezes, gerando tempo de execução exponencial (O(2^n)). A memória adicional (caching) reduz a complexidade para O(n), sem alterar a recursão.

Técnica	Descrição	Aplicabilidade ao problema	Efeito no tempo de execução
Memoization	Armazena resultados de chamadas anteriores para reutilização	✅ Elimina recálculos repetidos de mesmos argumentos	Reduz de O(2ⁿ) para O(n)
Tail recursion optimization	Otimiza chamadas recursivas em posição de cauda	❌ Fibonacci clássico não tem chamada em cauda	Não se aplica
Loop unrolling	Desenrola laços para reduzir overhead de controle	❌ Não ataca repetição de chamadas	Irrelevante para recursão
Branch prediction	Predição de desvios em hardware	❌ Não altera lógica do algoritmo	Não reduz chamadas redundantes
SIMD vectorization	Processamento paralelo de dados vetoriais	❌ Não se aplica a recursão sequencial	Não resolve o problema

Otimização recursiva: Problema: recálculo repetido (Fibonacci n=45, Complexidade exponencial O(2ⁿ)); Solução: memoization (Cache de resultados, Reduz para O(n), Mantém recursão); Técnicas inadequadas (Tail recursion (não é cauda), Loop unrolling (baixo nível), Branch prediction (hardware), SIMD (vetorização))

Alternativa A — ✅ Correta ⟵ GABARITO

Memoization (ou programação dinâmica top-down) é a técnica mais adequada para evitar recálculos repetidos. A ideia é criar um dicionário/array para armazenar o resultado de cada chamada com um argumento específico; antes de computar, verifica-se se o valor já foi calculado. Exemplo:

cache = {}
def fib(n):
    if n in cache: return cache[n]
    if n < 2: return n
    cache[n] = fib(n-1) + fib(n-2)
    return cache[n]

Alternativa B — ❌ Incorreta

Tail recursion optimization (otimização de recursão em cauda) é uma técnica aplicada por compiladores quando a chamada recursiva é a última operação da função. No Fibonacci clássico, a chamada recursiva não está em posição de cauda (são duas chamadas e uma soma), portanto a otimização não se aplica nem resolveria o problema de repetição de argumentos.

Alternativa C — ❌ Incorreta

Loop unrolling (desenrolamento de laços) é uma otimização de baixo nível que reduz o overhead de controle de loops, mas não ataca o problema de chamadas repetidas com mesmos argumentos. É irrelevante para algoritmos recursivos não iterativos.

Alternativa D — ❌ Incorreta

Branch prediction (predição de desvios) é uma técnica de hardware usada em pipelines de processadores para adivinhar o fluxo de execução de instruções condicionais. Não altera a lógica do algoritmo nem reduz chamadas redundantes.

Alternativa E — ❌ Incorreta

SIMD vectorization (vetorização SIMD) é uma técnica de paralelismo em nível de dados que processa múltiplos elementos simultaneamente usando instruções especiais. Não é aplicável a um algoritmo recursivo simples como Fibonacci, onde o gargalo é a repetição de chamadas, não o processamento de dados em lote.

PEGA ESSA DICA!

Ao identificar um algoritmo recursivo com repetição de cálculos (como Fibonacci), a primeira técnica a considerar é a memoization (programação dinâmica). Lembre-se de que tail recursion só ajuda se a chamada recursiva for a última operação da função e não houver múltiplas chamadas.

Gabarito: letra A