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()

Recursividade em Python: Somatório e Fatorial Usando Função Recursiva

"Para aprender recursividade, você precisa saber recursividade..."

Essa frase pode soar bem louca, a primeira vista.
Mas quando te ensinarmos melhor o conceito de uma função recursiva, ela vai fazer total sentido para você.

Somatório na Matemática

Definimos como somatório, uma função matemática representada por:
f(x) = 1 + 2 + 3 + ... + (x-1) + x

Ou seja, somamos tudo de 1 até o valor x.
Exemplos:
f(4) = 1 + 2 + 3 + 4 = 10
f(5) = 1 + 2 + 3 + 4 + 5 = 15
f(6) = 1 + 2 + 3 + 4 + 5 + 6 = 21
etc

Porém, note uma coisa:
f(5) = f(4) + 5 = 10 + 5 = 15
f(6) = f(5) + 6 = 15 + 6 = 21

Ou seja, podemos generalizar:
f(x) = f(x-1) + x

Agora, calma.
Vamos ver o motivo dessa teoria toda.

Função Recursiva em Python

Dizemos que uma função é recursiva quando, dentro dela, ela chama ela mesma.
Porém, com outro argumento.

No exemplo anterior, passamos um valor x para a função recursiva.
Ela soma x com o valor de f(x-1), ou seja, ela vai chamar ela mesma, mas ao invés de passar o parâmetro x, vai passar o parâmetro x-1.

E essa função que recebeu x-1 vai somar (x-1) com f(x-2), ou seja, chamou ela mesma novamente, mas agora com um parâmetro (x-2). E por aí vai.

Onde termina isso?
Ora, com f(1) = 1

Somatório com Função Recursiva

Se ainda está perdido, tudo bem, é pra estar mesmo.
Mas vamos resolver um exemplo que vai te fazer entender melhor.

Crie um script que peça um inteiro positivo para o usuário.
Em seguida, exiba a soma do somatório de 1 até esse número.

Nosso código fica assim:

def somatorio(x):
    if x==1:
        return 1
    else:
        return x + somatorio(x-1)

while True:
    x = int(input("Somatorio de 1 até: "))
    print("Soma: ",somatorio(x) )

Agora vamos ver o que faz linha por linha.

Primeiro, definimos nossa função, vai se chamar somatorio e recebe um valor como parâmetro, o x.
A primeira coisa a se fazer numa função recursiva é definir onde ela vai parar, ou seja, dizer "ei, chega, aqui você vai parar de invocar você mesma"

Nesse caso, é quando o argumento for 1, aí o somatório é 1 e retorna 1.
Se não for argumento 1, ai cai no ELSE, então o retorno é o próprio argumento x somado de somatorio(x-1).

Lembra da função f(x)? Agora ela se chama é somatorio:
somatorio(x) = x + somatorio(x-1)

E prontinho, no cordo do script pedimos um número ao usuário.
Por exemplo, se x =4 :

Primeiro return: 4 + somatorio(3)
Segundo return: 4 + 3 + somatorio(2)
Terceiro return: 4 + 3 + 2 + somatorio(1)
Quarto return: 4 + 3 + 2 + 1 = 10

Fatorial com Recursividade

Para calcularmos o fatorial de um inteiro n, basta multiplicarmos todos os números de 1 até o próprio n. Expressamos o fatorial de n por n !

Por exemplo:

• 4! = 4*3*2*1 = 24
• 5! = 5*4*3*2*1 = 120
• 6! = 6*5*4*3*2*1 = 720

Agora note duas coisas:
5! = 5 * 4!
6! = 6 * 5!

Ou seja:
n! = n * (n-1)!

Implementando isso em código Python:

def fatorial(x):
    if x==1:
        return 1
    else:
        return x * fatorial(x-1)

while True:
    x = int(input("Fatorial de: "))
    print("Fatorial: ",fatorial(x) )

O ponto de parada é quando a função recebe 1 como argumento.
Aí ela retorna 1.

Se não for 1, retorna o valor do argumento x multiplicado pelo fatorial de (x-1)!

Exercício Proposto: Fibonacci

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 ao usuário, n. Então uma função exibe todos os termos da sequência até o n-ésimo termo. Use recursividade.

Solução:
Gerar a sequência de Fibonacci