Como gerar a Sequência de Fibonacci com listas e recursão

 Neste tutorial, vamos aprender como criar um algoritmo que gera uma lista, em Python, com os números da série de Fibonacci:

Código da Sequência de Fibonacci em Python

Sem mais delongas, vamos ao algoritmo:

1. def fib(n):
2.     f0, f1 = 0, 1
3.     f = [1] * n
4.     for i in range(1, n):
5.         f[i] = f0 + f1
6.         f0, f1 = f1, f[i]
7.     return f
9. num = int(input("Quantos termos gerar: "))
10. print( fib(num) )

Diferente das outras vezes, que usamos o laço while e usando recursão com funções, dessa vez vamos usar listas.

Código comentado da Série de Fibonacci

Na linha 1, definimos a função fib(), que recebe um inteiro n, que é o número de termos que vamos gerar.

Os primeiros termos da série sempre são 0 e 1, armazenados nas variáveis f0 e f1.
E para os próximos termos? Bom, como teremos n termos, vamos criar uma lista f com n termos, isso foi feito na linha 3.

O próximo passo é aplicar nos próximos termos a regra da sequência de Fibonacci:
"Cada termo é a soma dos dois anteriores"

Como ja temos os termos f0 e f1, o próximo termo é a soma destes (linha 5).
Agora temos três termos: f0, f1 e f[i]

Na próxima iteração, o novo valor de f0 será o valor antigo de f1.
O novo valor de f1 será o valor anterior da lista f
E o novo valor da lista? É sempre a soma dos dois anteriores, que são f0 e f1.

• Benchmarking do algoritmo

Vamos usar os comandos %timeit e %time para analisar o tempo e execução para achar uma lista com os 100 primeiros termos da Série de Fibonacci como nosso algoritmo:

Veja que foram feitos 100.000 (cem mil!) loops, em poucos microssegundos! Ou seja, é um bom código.

Exercício:

Faça o mesmo benchmarking para o código usando apenas o laço while. E depois usando o código que usa apenas recursividade sem as listas.

E aí, qual deu melhor?