A sequência de Fibonacci é uma sequência numérica em que cada número é a soma dos dois anteriores, iniciando normalmente com 0 e 1 . Ou seja:
\begin{aligned} & F(\theta)=0 \\\ & F(1)=1 \\\ & F(n)=F(n-1)+F(n-2), \text { para } n \geq 2 \end{aligned}
(1.5pts) Versão Iterativa: Desenvolva uma função que utilize uma estrutura de repetição (por exemplo, for ou while) para calcular o valor de F(n) sem utilizar recursão.

Passo 1

O enunciado pede que eu desenvolva uma função que calcule o termo \,F(n)\, da sequência de Fibonacci usando uma estrutura de repetição (por exemplo, um \texttt{for} ou \texttt{while}), ou seja, sem usar recursão.
Informações dadas:
  • A sequência é definida por \;F(0)=0,\;F(1)=1\; e, para \;n\ge2, \;F(n)=F(n-1)+F(n-2).\n
    O que se pede:
  • Uma versão iterativa (uma função) que, dada uma entrada inteira \;n\ge0, retorne \;F(n) sem usar chamada recursiva.

Passo 2

Decidindo a estratégia (sem formalismos chatos): usar um laço que vá construindo os termos da sequência um a um. A ideia é manter só os dois últimos termos vistos e, a cada passo, atualizar para o próximo termo. Isso evita a explosão exponencial da recursão e usa memória constante.
Condições iniciais (casos base) que precisamos tratar antes do laço:
  • Se \;n=0 a resposta é \;F(0)=0.
  • Se \;n=1 a resposta é \;F(1)=1.
    Para \;n\ge2 usamos o laço para calcular.

Passo 3

Introduzindo as variáveis que vamos usar e o que elas significam:
  • Vou usar duas variáveis, que chamo aqui de \;a e \;b.
  • Em qualquer momento do laço, vou manter a invariante: \;a = F(i-2) e \;b = F(i-1) para algum índice \;i.
  • Para avançar um passo (ir de \;i-1 para \;i) eu calculo o novo termo como \;a+b e atualizo as variáveis para manter a invariante no próximo \;i: faço \;a \leftarrow b e \;b \leftarrow a+b (atenção: o \;a da direita é o valor antigo de \;a).

Passo 4

Descrevendo o laço mais explicitamente (pseudopasso a passo):
  1. Trato os casos \;n=0 e \;n=1 retornando \;0 e \;1 respectivamente.
  2. Inicializo \;a=0 e \;b=1. Nesse momento a invariante vale para \;i=1: \;a=F(-1) não é interessante; pense que antes do primeiro passo efetivo temos \;a=F(0) e \;b=F(1).
  3. Para cada \;i indo de \;2 até \;n (inclusive), faço:
    • calcular \;c = a + b (que é F(i));
    • atualizar \;a \leftarrow b e \;b \leftarrow c.
  4. Ao final do laço, \;b contém \;F(n). Retorno \;b.

Passo 5

Exemplo concreto (vamos “mastigar” os valores para \;n=5 para você ver que o laço funciona):
  • Início: \;a=0,\;b=1.
  • Iteração para \;i=2: \;c=a+b=0+1=1. Atualiza: \;a\leftarrow1,\;b\leftarrow1. Agora \;a=1,\;b=1.
  • Iteração para \;i=3: \;c=1+1=2. Atualiza: \;a\leftarrow1,\;b\leftarrow2. Agora \;a=1,\;b=2.
  • Iteração para \;i=4: \;c=1+2=3. Atualiza: \;a\leftarrow2,\;b\leftarrow3. Agora \;a=2,\;b=3.
  • Iteração para \;i=5: \;c=2+3=5. Atualiza: \;a\leftarrow3,\;b\leftarrow5. Agora \;b=5 que é \;F(5).
    Isso bate com a sequência conhecida \;0,1,1,2,3,5,\dots.

Passo 6

Justificativa formal curta (invariante do laço — por que isso sempre dá certo):
  • Base: antes do primeiro passo efetivo temos \;a=0=F(0) e \;b=1=F(1).
  • Passo do laço: suponha que, no início de uma iteração para índice \;i, tenhamos \;a=F(i-2) e \;b=F(i-1). Calculamos \;c=a+b. Então \;c=F(i-2)+F(i-1)=F(i) pela definição da sequência. Ao fazer \;a\leftarrow b e \;b\leftarrow c passamos a ter \;a=F(i-1) e \;b=F(i), que é exatamente a invariante para o próximo índice. Portanto, após terminar em \;i=n, \;b=F(n).

Passo 7

Complexidade e observações práticas:
  • Tempo: o laço executa \;n-1 atualizações no pior caso ( \;n\ge2), ou seja tempo \;O(n).
  • Espaço: usamos um número constante de variáveis, espaço \;O(1).
  • Caso de entrada inválida: se alguém chamar a função com \;n<0 devemos tratar (por exemplo, lançar erro) — normalmente Fibonacci é definido para \;n\ge0.
  • Se precisar de Fibonacci para \;n muito grande, lembre que os valores crescem rápido; pode ser necessário usar tipos de inteiros que suportem muitos dígitos (em Python int é automático).

Resposta

def fibonacci_iterativa(n):
“”"
Retorna F(n) da sequência de Fibonacci de forma iterativa (sem recursão).
Assume n inteiro >= 0. Levanta ValueError se n < 0.
“”"
if n < 0:
raise ValueError(“n deve ser inteiro não-negativo”)
if n == 0:
return 0
if n == 1:
return 1
a = 0
b = 1
for i in range(2, n + 1):
c = a + b
a = b
b = c
return b

Exercícios relacionados