Python Progressivo

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:

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

"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

Recursividade em Programação Python - o que é