Como usar a sequência de Fibonacci em Python?

[

Um Guia Python para a Sequência Fibonacci

Neste tutorial, você aprenderá:

• Gerar a sequência Fibonacci usando um algoritmo recursivo
• Otimizar o algoritmo recursivo Fibonacci usando memoização
• Gerar a sequência Fibonacci usando um algoritmo iterativo

Vamos começar!

Começando com a Sequência Fibonacci

Leonardo Fibonacci foi um matemático italiano que conseguiu rapidamente produzir uma resposta para a seguinte 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á origem 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 seguinte sequência:

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 conheciam essa sequência desde o século VI, e Fibonacci a utilizou para calcular o crescimento das populações de coelhos.

Vamos agora ver como gerar a sequência Fibonacci usando Python.

Examinando a Recursão Por Trás da Sequência Fibonacci

A sequência Fibonacci pode ser definida de forma recursiva, o que significa que cada número na sequência é calculado a partir da soma dos dois números anteriores.

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

Neste exemplo de código Python, a função fibonacci() recebe um número n como argumento e retorna o número da sequência Fibonacci correspondente. O caso base ocorre quando n é igual a 0 ou 1, em que caso a própria função retorna n. Caso contrário, a função chama a si mesma recursivamente com n-1 e n-2 e retorna a soma dos resultados.

Vamos testar a função fibonacci() para verificar se ela está gerando a sequência corretamente:

print(fibonacci(0))  # 0
print(fibonacci(1))  # 1
print(fibonacci(2))  # 1
print(fibonacci(3))  # 2
print(fibonacci(4))  # 3
print(fibonacci(5))  # 5

Ao executar esse código, você verá que ele imprime os primeiros números da sequência Fibonacci. No entanto, se você chamar a função fibonacci() com um valor grande, como fibonacci(50), você notará que a função leva muito tempo para retornar um resultado. Isso ocorre porque a implementação recursiva não é eficiente e recalcula os mesmos números várias vezes.

Vamos agora otimizar o algoritmo recursivo para torná-lo mais eficiente.

Gerando a Sequência Fibonacci de Forma Recursiva em Python

Uma das maneiras de otimizar o algoritmo recursivo para gerar a sequência Fibonacci é usar a técnica de memoização. A memoização envolve armazenar os resultados dos cálculos anteriores em uma estrutura de dados, como um dicionário, para que não seja necessário recalcular os mesmos valores novamente.

def fibonacci(n, memo={}):
    if n <= 1:
        return n
    elif n not in memo:
        memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

Nesta nova versão do código, a função fibonacci() agora recebe um argumento adicional chamado memo, que é um dicionário vazio por padrão. A função verifica se o valor n já existe no dicionário memo. Se o valor não estiver presente, a função calcula recursivamente o número da sequência Fibonacci normalmente e armazena o resultado no dicionário. Se o valor já estiver presente no dicionário, a função simplesmente retorna o valor armazenado.

Vamos testar novamente a função fibonacci() para ver se ela é mais eficiente agora:

print(fibonacci(50))  # 12586269025

Você verá que o cálculo é executado muito mais rapidamente, pois os valores intermediários são armazenados em memo e podem ser reutilizados quando necessário.

A memoização é uma técnica poderosa para otimizar algoritmos recursivos, como a geração da sequência Fibonacci. No entanto, vamos explorar agora uma abordagem iterativa para gerar a sequência Fibonacci.

Gerando a Sequência Fibonacci em Python

Outra maneira de gerar a sequência Fibonacci é usando um algoritmo iterativo. Em vez de usar recursão, podemos usar um loop para calcular cada número da sequência um após o outro.

def fibonacci(n):
    sequence = [0, 1]
    while len(sequence) < n + 1:
        next_number = sequence[-1] + sequence[-2]
        sequence.append(next_number)
    return sequence[n]

Neste exemplo de código, a função fibonacci() recebe um número n como argumento e retorna o número correspondente da sequência Fibonacci. A função começa criando uma lista sequence contendo os primeiros dois números da sequência, 0 e 1. Em seguida, ela entra em um loop que continua até que o comprimento da lista sequence seja igual a n + 1, o que significa que o número desejado da sequência foi calculado.

A cada iteração do loop, a função calcula o próximo número da sequência Fibonacci somando os dois últimos números da lista sequence, e depois adiciona esse número à lista. Depois que o loop termina, a função retorna o número desejado, que é o n-ésimo número na lista sequence.

Vamos testar a função fibonacci() para verificar se ela está gerando a sequência corretamente:

print(fibonacci(0))  # 0
print(fibonacci(1))  # 1
print(fibonacci(2))  # 1
print(fibonacci(3))  # 2
print(fibonacci(4))  # 3
print(fibonacci(5))  # 5

Ao executar esse código, você verá que ele imprime os primeiros números da sequência Fibonacci novamente. A vantagem dessa abordagem iterativa é que ela é mais eficiente do que a abordagem recursiva, pois não precisa armazenar os valores intermediários.

Conclusão

Neste tutorial, você aprendeu como gerar a sequência Fibonacci usando Python. Você viu uma implementação recursiva e como otimizá-la usando memoização. Você também aprendeu uma abordagem iterativa para gerar a sequência Fibonacci. Essas técnicas são úteis para entender e lidar com algoritmos recursivos e para melhorar a eficiência de seus programas.

A sequência Fibonacci é apenas um exemplo de como a matemática pode ser aplicada em problemas de programação. Explorar e entender essas sequências pode ajudá-lo a desenvolver habilidades mais avançadas em programação e resolução de problemas.

Esperamos que este tutorial tenha sido útil para você e que você possa aplicar o conhecimento adquirido em suas próprias aplicações em Python. Continue praticando e explorando novos conceitos para se tornar um programador Python mais habilidoso.

Keep calm and code in Python!

Aprenda mais sobre Python com nossos tutoriais e cursos interativos

Become a Member to Unlock All Content