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?

Gerar a Série de Fibonacci em Python (Recursividade)

Neste tutorial de nosso Curso de Python, vamos aprender como gerar a tão famosa sequência de Fibonacci, usando funções e recursão!

É um exercício resolvido de nossa lista de questões de funções.
Leia também:

• Certificado do Curso de Python (para quem deseja trabalhar como programador)
• Conteúdo do Python Progressivo em PDF

Gerando a Sequência de Fibonacci em Python

A série de Fibonacci é uma sequência de números, cujos dois primeiros são 0 e 1. O termo seguinte da sequência é obtido somando os dois anteriores. Faça uma script em Python que solicite um inteiro positivo maior que 1 ao usuário, n. Então uma função exibe todos os termos da sequência até o n-ésimo termo. Use recursividade.

Vamos criar uma função chamada fibo( n ) que tem o parâmetro n.
O argumento que você deve passar para esta função é um inteiro positivo, maior ou igual a 2.

Como a série de Fibonacci é formada somando seus dois termos anteriores, sua fórmula geral é:

fibo(n) = fibo(n-1) + fibo(n-2)

Mas como toda boa função que usa recursividade, ele tem que ter um stop, pois uma hora ela vai ter que parar. Fazemos isso usando testes condicionais IF.

No nosso caso, vai ter dois stops.
Se o valor de n for igual 1, vamos retornar 0 (pois o primeiro termo é 0).
Se o valor de n for igual 2, vamos retornar 1 (pois o segundo termo é 1).

Pronto, para valores maiores que 2, basta somarmos os dois termos anteriores.

Agora vamos montar nossa função menu().
Ela pede o termo n ao usuário, que deve ser inteiro e maior que 2.

Agora ela deve imprimir na tela os valores de fibo(1), fibo(2), fibo(3)....até fibo(n).
Lembre-se, nossa função mostra o n-ésimo termo!

Então temos que imprimir todos, de 1 até n.
Fazemos isso usando um laço for, que vai de 1 até n (função range). 

E prontinho, vai exibir cada termo da sequência de Fibonacci, um por linha!

Danada essa função recursiva, não?

Código Python

Nosso código ficou assim:

def fibo(n):
    if n==1:
        return 0
    elif n==2:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)
        
def menu():
    n = int(input('Exibir ate o termo (maior que 2): '))

    for val in range(1,n+1):
        print(fibo(val))
    
while True:
    menu()