Como Usar a Série de Fibonacci no Python?

[

Um Guia Python para a Sequência de Fibonacci

A sequência de Fibonacci é uma sequência muito famosa de números inteiros. A sequência surge naturalmente em muitos problemas e possui uma definição recursiva interessante. Aprender como gerá-la é um passo essencial na jornada do programador pragmático em direção ao domínio da recursão. Neste tutorial, você aprenderá o que é a sequência de Fibonacci e como gerá-la usando Python.

Introdução à Sequência de Fibonacci

Leonardo Fibonacci foi um matemático italiano que conseguiu rapidamente produzir uma resposta para essa pergunta feita pelo Imperador Frederick II da Suábia: “Quantos pares de coelhos são obtidos em um ano, excluindo os casos de morte, supondo que cada casal dá à luz a outro casal a cada mês e que os casais mais jovens já são capazes de se reproduzir no segundo mês de vida?”

A resposta foi a sequência seguinte:

1, 1, 2, 3, 5, 8, 13, 21, …

O padrão começa após os dois primeiros números, 0 e 1, onde cada número na sequência é sempre a soma dos dois números anteriores. Matemáticos indianos já conheciam essa sequência desde o século VI, e Fibonacci aproveitou para calcular o crescimento das populações de coelhos.

Gerando a Sequência de Fibonacci Recursivamente em Python

Vamos começar gerando a sequência de Fibonacci usando um algoritmo recursivo. Um algoritmo recursivo é aquele que se chama a si mesmo para resolver um problema menor.

def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

Nesse exemplo, a função fib recebe um número n e retorna o n-ésimo número da sequência de Fibonacci. Se n for 0 ou 1, a função retorna n imediatamente. Caso contrário, ela chama a si mesma para obter os dois números anteriores da sequência e retorna a sua soma.

Podemos testar essa função chamando-a com diferentes valores de n:

print(fib(0))  # Saída: 0
print(fib(1))  # Saída: 1
print(fib(10))  # Saída: 55

Otimizando o Algoritmo Recursivo para a Sequência de Fibonacci

Embora o algoritmo recursivo funcione, ele é extremamente ineficiente para valores grandes de n. Isso ocorre porque ele recalcula os mesmos valores repetidamente. Vamos utilizar uma técnica chamada memoização para otimizar o algoritmo.

Memoizando o Algoritmo Recursivo

A memoização é uma técnica que envolve o armazenamento dos cálculos já realizados para evitar repetições desnecessárias. Podemos usar um dicionário Python para armazenar os valores já calculados.

cache = {}

def fib(n):
    if n in cache:
        return cache[n]
    elif n <= 1:
        result = n
    else:
        result = fib(n-1) + fib(n-2)

    cache[n] = result
    return result

Nesse exemplo, adicionamos um dicionário chamado cache para armazenar os valores já calculados. Sempre que chamamos a função fib, verificamos se o valor já está presente no cache. Se estiver, retornamos o valor armazenado. Caso contrário, realizamos o cálculo normalmente, armazenamos o resultado no cache e retornamos o resultado.

Podemos testar a função novamente e comparar o desempenho:

print(fib(30))  # Saída: 832040
print(fib(50))  # Saída: 12586269025

Gerando a Sequência de Fibonacci em Python

Agora que otimizamos o algoritmo recursivo, podemos explorar outras formas de gerar a sequência de Fibonacci.

Usando Recursão e uma Classe Python

class Fibonacci:
    def __init__(self):
        self.cache = {0: 0, 1: 1}

    def fib(self, n):
        if n in self.cache:
            return self.cache[n]
        else:
            result = self.fib(n-1) + self.fib(n-2)
            self.cache[n] = result
            return result

Nesse exemplo, encapsulamos a lógica da sequência de Fibonacci em uma classe chamada Fibonacci. A classe possui um dicionário cache para armazenar os valores já calculados. A função fib utiliza a mesma lógica de memoização que vimos anteriormente.

Podemos utilizar a classe dessa forma:

fibonacci = Fibonacci()
print(fibonacci.fib(20))  # Saída: 6765
print(fibonacci.fib(40))  # Saída: 102334155

Usando Iteração e uma Função Python

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Nesse exemplo, utilizamos uma abordagem iterativa para gerar a sequência de Fibonacci. Utilizamos duas variáveis, a e b, para armazenar os dois últimos números da sequência. A cada iteração, atualizamos essas variáveis e continuamos o loop. No final, retornamos a, que será o n-ésimo número da sequência.

Podemos testar essa função:

print(fib(15))  # Saída: 610
print(fib(25))  # Saída: 75025

Conclusão

Neste tutorial, você aprendeu o que é a sequência de Fibonacci e explorou diferentes formas de gerá-la usando Python. Começamos com um algoritmo recursivo simples e, em seguida, otimizamos o mesmo usando memoização. Também vimos como gerar a sequência de Fibonacci utilizando uma classe e uma função iterativa. Esperamos que essas informações sejam úteis em seus estudos e projetos futuros.