Implemente uma função que recebe um índice
, correspondente ao
-ésimo elemento da sequência de Fibonacci, e que retorna o valor do respectivo elemento da sequência. Faça tanto uma implementação iterativa, quanto uma recursiva.
Passo 1
O que o enunciado pede e quais são os dados:
- Entrada: um índice
(um número inteiro que indica o -ésimo elemento da sequência de Fibonacci). - Saída: o valor do elemento de Fibonacci correspondente a esse índice.
- Convenção adotada aqui (vou explicar e usar esta convenção ao longo da resolução): a sequência será a versão padrão
e para todo
Ou seja,
.
- O enunciado pede duas implementações: uma iterativa e uma recursiva. Vou implementar ambas em Python e explicar passo a passo o raciocínio, os casos-base, a correção e a análise de complexidade. Também darei exemplos numéricos para ficar claro como executar na “hora da prova”.
Passo 2
Entendendo a definição e os casos-base (a teoria que você precisa dominar)
- A definição recursiva da sequência de Fibonacci é exatamente a fórmula que vamos traduzir para código:
- Significado de cada símbolo:
-
é o índice (inteiro, assumimos ). -
é o valor da sequência de Fibonacci no índice .
-
- Casos-base: são os valores que param a recursão:
e . Em qualquer implementação recursiva sempre trate explicitamente esses casos para evitar recursões infinitas. - Observação prática: algumas questões usam índice começando em 1 (com
); aqui usei a convenção . Se na sua prova a convenção for a outra, basta deslocar indices (por exemplo, pedir -ésimo com e retornar do meu código).]
Passo 3
Implementação iterativa — ideia e passo a passo didático
- Ideia: usar um laço que constrói os Fibonacci de baixo para cima (programação dinâmica “bottom-up”). Mantém só dois valores atuais, porque para calcular
basta conhecer e . - Variáveis que vou usar:
-
para guardar , -
para guardar , - na iteração atual calculo
que é , e então atualizo , .
-
- Estrutura do algoritmo:
- Se
retorne . - Se
retorne . - Inicialize
(que representa ), (que representa ). - Para
de até faça: ; depois ; . - Ao final,
contém ; retorne .
- Se
- Complexidade:
- Tempo:
, porque o laço itera vezes. - Espaço extra:
, só duas/três variáveis além da entrada.
- Tempo:
- Exemplo passo a passo com
:- Inicial:
( ), ( ). - i=2:
→ atualiza , (agora ). - i=3:
→ , (agora ). - i=4:
→ , (agora ). - i=5:
→ , (agora ). - i=6:
→ , (agora ). - Retorna
, que é .
- Inicial:
Implementação iterativa em Python:
def fib_iter(k):
"""
Retorna F_k onde F_0 = 0, F_1 = 1 e F_k = F_{k-1} + F_{k-2}.
Entrada: k (int, k >= 0)
Saída: inteiro F_k
"""
if k < 0:
raise ValueError("k deve ser inteiro não negativo")
if k == 0:
return 0
if k == 1:
return 1
a, b = 0, 1 # a = F_0, b = F_1
for _ in range(2, k + 1):
c = a + b # c = F_i
a, b = b, c
return b
Passo 4
Implementação recursiva (forma direta) — ideia e passo a passo didático
- Ideia: traduzir literalmente a definição recursiva para código: se
for 0 ou 1, retorna os casos-base; caso contrário retorna somatória das chamadas recursivas para e . - Estrutura:
- Se
retorne . - Se
retorne . - Caso contrário retorne fib_rec(
) + fib_rec( ).
- Se
- Atenção: essa implementação é simples, mas ineficiente; recalcula muitas subproblemas repetidas vezes.
- Análise de complexidade do método recursivo ingênuo:
- O tempo cresce aproximadamente como a sequência geométrica com razão
(a razão áurea, ): tempo — isso é exponencial em . - A profundidade de recursão é
(consumo de pilha).
- O tempo cresce aproximadamente como a sequência geométrica com razão
- Exemplo: para
a chamada produz a árvore de chamadas que calcula várias vezes valores iguais (por exemplo, é calculado várias vezes).
Implementação recursiva direta em Python:
def fib_rec(k):
"""
Implementação recursiva direta (ineficiente) de Fibonacci.
Entrada: k (int, k >= 0)
Saída: inteiro F_k
"""
if k < 0:
raise ValueError("k deve ser inteiro não negativo")
if k == 0:
return 0
if k == 1:
return 1
return fib_rec(k - 1) + fib_rec(k - 2)
Passo 5
Por que a versão recursiva ingênua é ruim na prática — e a melhoria prática (memoização)
- Problema: muitas subchamadas repetidas (por exemplo, ao calcular
a função calcula várias vezes). - Solução natural: memoização (armazenar resultados já calculados) — transforma a recursão exponencial em linear em tempo.
- A memoização ainda é uma versão “recursiva” (usa recursão), mas com complexidade
e espaço extra para o dicionário/memo. - Implementação com memoização (opcional, altamente recomendada para provas quando pedem recursiva eficiente):
Implementação recursiva com memoização em Python:
def fib_rec_memo(k, memo=None):
"""
Recursão com memoização: tempo O(k), espaço O(k).
Entrada: k (int, k >= 0)
Saída: inteiro F_k
"""
if k < 0:
raise ValueError("k deve ser inteiro não negativo")
if memo is None:
memo = {0: 0, 1: 1}
if k in memo:
return memo[k]
memo[k] = fib_rec_memo(k - 1, memo) + fib_rec_memo(k - 2, memo)
return memo[k]
Passo 6
Dicas práticas e pontos para a prova (como escrever rapidamente e evitar erros)
- Sempre trate casos-base explicitamente (
e ). - Se a prova pede “recursiva” e não aceita otimização, implemente a recursiva direta e comente que é exponencial; se aceitarem otimização, use memoização.
- Se for pedido o melhor método para grandes
, use a abordagem iterativa (ou técnicas mais avançadas: exponenciação de matrizes ou fórmula de Binet com cuidado numérico). A exponenciação de matrizes dá e é útil para k muito grande; a fórmula de Binet envolve números reais e erros de arredondamento. - Em Python não precisa se preocupar com overflow de inteiros (inteiros arbitrariamente grandes), mas em linguagens com inteiro limitado (C/C++/Java) tome cuidado com overflow.
Resposta
def fib_iter(k):
“”"
Retorna F_k onde F_0 = 0, F_1 = 1 e F_k = F_{k-1} + F_{k-2}.
Entrada: k (int, k >= 0)
Saída: inteiro F_k
“”"
if k < 0:
raise ValueError(“k deve ser inteiro não negativo”)
if k == 0:
return 0
if k == 1:
return 1
a, b = 0, 1
for _ in range(2, k + 1):
c = a + b
a, b = b, c
return b
“”"
Retorna F_k onde F_0 = 0, F_1 = 1 e F_k = F_{k-1} + F_{k-2}.
Entrada: k (int, k >= 0)
Saída: inteiro F_k
“”"
if k < 0:
raise ValueError(“k deve ser inteiro não negativo”)
if k == 0:
return 0
if k == 1:
return 1
a, b = 0, 1
for _ in range(2, k + 1):
c = a + b
a, b = b, c
return b
def fib_rec(k):
“”"
Implementação recursiva direta (ineficiente) de Fibonacci.
Entrada: k (int, k >= 0)
Saída: inteiro F_k
“”"
if k < 0:
raise ValueError(“k deve ser inteiro não negativo”)
if k == 0:
return 0
if k == 1:
return 1
return fib_rec(k - 1) + fib_rec(k - 2)
“”"
Implementação recursiva direta (ineficiente) de Fibonacci.
Entrada: k (int, k >= 0)
Saída: inteiro F_k
“”"
if k < 0:
raise ValueError(“k deve ser inteiro não negativo”)
if k == 0:
return 0
if k == 1:
return 1
return fib_rec(k - 1) + fib_rec(k - 2)