Implemente uma função que recebe um índice k, correspondente ao k-é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 k (um número inteiro que indica o k-é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
F_0 = 0,\qquad F_1 = 1,
e para todo k\ge 2
F_k = F_{k-1} + F_{k-2}.
Ou seja, F_0=0, F_1=1, F_2=1, F_3=2, F_4=3, F_5=5,\dots.
  • 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:
F_k = \begin{cases} 0, & k=0,\\[4pt] 1, & k=1,\\[4pt] F_{k-1}+F_{k-2}, & k\ge 2. \end{cases}
  • Significado de cada símbolo:
    • k é o índice (inteiro, assumimos k\ge 0).
    • F_k é o valor da sequência de Fibonacci no índice k.
  • Casos-base: são os valores que param a recursão: F_0 e F_1. 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 F_1=1, F_2=1); aqui usei a convenção F_0=0. Se na sua prova a convenção for a outra, basta deslocar indices (por exemplo, pedir k-ésimo com k\ge1 e retornar F_{k-1} 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 F_k basta conhecer F_{k-1} e F_{k-2}.
  • Variáveis que vou usar:
    • a para guardar F_{i-2},
    • b para guardar F_{i-1},
    • na iteração atual calculo c = a + b que é F_i, e então atualizo a\leftarrow b, b\leftarrow c.
  • Estrutura do algoritmo:
    1. Se k=0 retorne 0.
    2. Se k=1 retorne 1.
    3. Inicialize a=0 (que representa F_0), b=1 (que representa F_1).
    4. Para i de 2 até k faça: c=a+b; depois a=b; b=c.
    5. Ao final, b contém F_k; retorne b.
  • Complexidade:
    • Tempo: \mathcal{O}(k), porque o laço itera k-1 vezes.
    • Espaço extra: \mathcal{O}(1), só duas/três variáveis além da entrada.
  • Exemplo passo a passo com k=6:
    • Inicial: a=0 ( F_0), b=1 ( F_1).
    • i=2: c=0+1=1 → atualiza a=1, b=1 (agora b=F_2).
    • i=3: c=1+1=2 a=1, b=2 (agora b=F_3).
    • i=4: c=1+2=3 a=2, b=3 (agora b=F_4).
    • i=5: c=2+3=5 a=3, b=5 (agora b=F_5).
    • i=6: c=3+5=8 a=5, b=8 (agora b=F_6).
    • Retorna 8, que é F_6.
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 k for 0 ou 1, retorna os casos-base; caso contrário retorna somatória das chamadas recursivas para k-1 e k-2.
  • Estrutura:
    1. Se k=0 retorne 0.
    2. Se k=1 retorne 1.
    3. Caso contrário retorne fib_rec( k-1) + fib_rec( k-2).
  • 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 \varphi (a razão áurea, \varphi\approx 1{,}618): tempo \Theta(\varphi^k) — isso é exponencial em k.
    • A profundidade de recursão é \mathcal{O}(k) (consumo de pilha).
  • Exemplo: para k=5 a chamada produz a árvore de chamadas que calcula várias vezes valores iguais (por exemplo, F_2 é 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 F_6 a função calcula F_4 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 \mathcal{O}(k) e espaço \mathcal{O}(k) 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 ( k=0 e k=1).
  • 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 k, 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á \mathcal{O}(\log k) 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
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)

Exercícios relacionados