欧博ABG官网-欧博官方网址-会员登入

Um guia Python para a sequência de Fibonacci

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

Neste tutorial, você aprenderá como:

Gere a sequência de Fibonacci usando um algoritmo recursivo

Otimize o algoritmo recursivo de Fibonacci usando memoização

Gere a sequência de Fibonacci usando um algoritmo iterativo

Para aproveitar ao máximo este tutorial, você deve conhecer os fundamentos da notação Big O, programação orientada a objetos, métodos especiais do Python, instruções condicionais, funções e estruturas de dados básicas como listas, filas e pilhas. Ter alguma familiaridade com esses conceitos o ajudará muito a entender os novos conceitos que explorará neste tutorial.

Vamos mergulhar de cabeça!

Introdução à sequência de Fibonacci

Leonardo Fibonacci foi um matemático italiano que conseguiu responder rapidamente a esta pergunta feita pelo imperador Frederico II da Suábia: “Quantos pares de coelhos são obtidos num ano, excluindo os casos de morte, supondo que cada casal dê à luz outro casal todos os meses e que os casais mais jovens conseguem reproduzir já 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. Os matemáticos indianos conheciam esta sequência desde o século VI, e Fibonacci aproveitou-a para calcular o crescimento das populações de coelhos.

F(n) é usado para indicar o número de pares de coelhos presentes no mês n, então a sequência pode ser expressa assim:

Na terminologia matemática, você chamaria isso de relação de recorrência, o que significa que cada termo da sequência (além de 0 e 1) é uma função dos termos anteriores.

Há também uma versão da sequência em que os dois primeiros números são 1, assim:

Nesta versão alternativa, F(0) ainda é implicitamente 0, mas você começa com F(1) e F(2). O algoritmo permanece o mesmo porque você sempre soma os dois números anteriores para obter o próximo número na sequência.

Para os fins deste tutorial, você usará a versão da sequência que começa com 0.

Examinando a recursão por trás da sequência de Fibonacci

Gerar a sequência de Fibonacci é um problema recursivo clássico. Recursão é quando uma função se refere a si mesma para analisar o problema que está tentando resolver. Em cada chamada de função, o problema se torna menor até atingir um caso base, após o qual ele retornará o resultado para cada chamador intermediário até retornar o resultado final ao chamador original.

Se você quisesse calcular o número de Fibonacci F(5), você precisaria calcular seus antecessores, F(4) e F( 3), primeiro. E para calcular F(4) e F(3), você precisaria calcular seus antecessores. A divisão de F(5) em subproblemas menores ficaria assim:

Cada vez que a função Fibonacci é chamada, ela é dividida em dois subproblemas menores porque foi assim que você definiu a relação de recorrência. Quando atinge o caso base de F(0) ou F(1), ele pode finalmente retornar um resultado ao seu chamador.

Para calcular o quinto número da sequência de Fibonacci, você resolve problemas menores, mas idênticos, até chegar aos casos base, onde pode começar a retornar um resultado:

Os subproblemas coloridos neste diagrama representam soluções repetitivas para o mesmo problema. Se você subir na árvore, encontrará mais dessas soluções repetitivas. Isso significa que para gerar uma sequência de Fibonacci recursivamente, é necessário calcular muitos números intermediários repetidamente. Esta é uma das questões fundamentais na abordagem recursiva da sequência de Fibonacci.

Gerando a sequência de Fibonacci recursivamente em Python

O algoritmo mais comum e mínimo para gerar a sequência de Fibonacci requer que você codifique uma função recursiva que se chama quantas vezes forem necessárias até calcular o número de Fibonacci desejado:

>>> def fibonacci_of(n): ... if n in {0, 1}: # Base case ... return n ... return fibonacci_of(n - 1) + fibonacci_of(n - 2) # Recursive case ... >>> [fibonacci_of(n) for n in range(15)] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Dentro de fibonacci_of(), você primeiro verifica o caso base. Em seguida, você retorna a soma dos valores resultantes da chamada da função com os dois valores anteriores de n. A compreensão da lista no final do exemplo gera uma sequência de Fibonacci com os primeiros quinze números.

Esta função cai rapidamente no problema de repetição que você viu na seção acima. A computação fica cada vez mais cara à medida que n fica maior. O tempo necessário aumenta exponencialmente porque a função calcula muitos subproblemas idênticos repetidamente.

Nota: Não tente esta função em casa com um número maior que 50. Dependendo do seu hardware, você pode esperar muito tempo antes de ver o resultado - se conseguir chegar até o fim.

Para calcular F(5), fibonacci_of() precisa chamar a si mesmo quinze vezes. Para calcular F(n), a profundidade máxima da árvore de chamadas é n, e como cada chamada de função produz duas chamadas de função adicionais, o a complexidade de tempo desta função recursiva é O(2n).

A maioria dessas chamadas é redundante porque você já calculou seus resultados. F(3) aparece duas vezes e F(2) aparece três vezes. F(1) e F(0) são casos básicos, então não há problema em chamá-los várias vezes. Talvez você queira evitar esse desperdício de repetição, que é o tema das seções a seguir.

Otimizando o Algoritmo Recursivo para a Sequência de Fibonacci

Existem pelo menos duas técnicas que você pode usar para tornar o algoritmo que gera a sequência de Fibonacci mais eficiente - em outras palavras, para fazer com que seu cálculo leve menos tempo. Essas técnicas garantem que você não fique calculando os mesmos valores repetidamente, o que tornou o algoritmo original tão ineficiente. Eles são chamados de memoização e iteração.

Memorizando o Algoritmo Recursivo

Como você viu no código acima, a função Fibonacci chama a si mesma várias vezes com a mesma entrada. Em vez de uma nova chamada toda vez, você pode armazenar os resultados das chamadas anteriores em algo como um cache de memória. Você pode usar uma lista Python para armazenar os resultados de cálculos anteriores. Essa técnica é chamada de memoização.

A memorização acelera a execução de funções recursivas caras, armazenando resultados previamente calculados em um cache. Desta forma, quando a mesma entrada ocorrer novamente, a função só terá que procurar o resultado correspondente e retorná-lo sem ter que executar o cálculo novamente. Você pode se referir a esses resultados como armazenados em cache ou memorizados:

Com a memoização, você só precisa percorrer a árvore de chamadas de profundidade n uma vez após retornar do caso base, enquanto recupera todos os valores calculados anteriormente destacados em amarelo, F (2) e F(3), do cache anterior.

O caminho laranja mostra que nenhuma entrada da função Fibonacci é chamada mais de uma vez. Isso reduz significativamente a complexidade de tempo do algoritmo de exponencial O(2n) para linear O(n).

Mesmo para os casos base, você pode substituir a chamada de F(0) e F(1) apenas pela recuperação dos valores diretamente do cache nos índices 0 e 1, para que você acabo chamando a função apenas seis vezes em vez de quinze!

Aqui está uma possível tradução dessa otimização para o código Python:

>>> cache = {0: 0, 1: 1} >>> def fibonacci_of(n): ... if n in cache: # Base case ... return cache[n] ... # Compute and cache the Fibonacci number ... cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2) # Recursive case ... return cache[n] >>> [fibonacci_of(n) for n in range(15)] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Neste exemplo, você usa um dicionário Python para armazenar em cache os números de Fibonacci calculados. Inicialmente, cache contém os valores iniciais da sequência de Fibonacci, 0 e 1. Dentro da função, você primeiro verifica se o número de Fibonacci para o valor de entrada atual de n já está em cache. Nesse caso, você retorna o número em questão.

Se não houver nenhum número de Fibonacci para o valor atual de n, então você o calcula chamando fibonacci_of() recursivamente e atualizando cache. A etapa final é retornar o número Fibonacci solicitado.

Explorando um algoritmo iterativo

E se você nem precisar chamar a função recursiva de Fibonacci? Na verdade, você pode usar um algoritmo iterativo para calcular o número na posição n na sequência de Fibonacci.

Você sabe que os dois primeiros números da sequência são 0 e 1 e que cada número subsequente na sequência é a soma de seus dois antecessores anteriores. Então, você pode simplesmente criar um loop que some os dois números anteriores, n - 1 e n - 2, juntos para encontrar o número na posição n na sequência.

Os números roxos em negrito no diagrama abaixo representam os novos números que precisam ser calculados e adicionados ao cache em cada etapa iterativa:

Para calcular o número de Fibonacci na posição n, você armazena os dois primeiros números da sequência, 0 e 1, em cache. Em seguida, calcule os próximos números consecutivamente até retornar cache[n].

Gerando a sequência de Fibonacci em Python

Agora que você conhece o básico de como gerar a sequência de Fibonacci, é hora de se aprofundar e explorar ainda mais as diferentes maneiras de implementar o algoritmo subjacente em Python. Nas seções a seguir, você explorará como implementar diferentes algoritmos para gerar a sequência de Fibonacci usando recursão, programação orientada a objetos Python e também iteração.

Usando recursão e uma classe Python

Sua primeira abordagem para gerar a sequência de Fibonacci usará uma classe Python e recursão. Uma vantagem de usar a classe sobre a função recursiva memorizada que você viu antes é que uma classe mantém estado e comportamento (encapsulamento) juntos dentro do mesmo objeto. No exemplo da função, entretanto, cache é um objeto completamente separado, portanto você não tem controle sobre ele.

Abaixo está o código que implementa sua solução baseada em classe:

# fibonacci_class.py class Fibonacci: def __init__(self): self.cache = [0, 1] def __call__(self, n): # Validate the value of n if not (isinstance(n, int) and n >= 0): raise ValueError(f'Positive integer number expected, got "{n}"') # Check for computed Fibonacci numbers if n < len(self.cache): return self.cache[n] else: # Compute and cache the requested Fibonacci number fib_number = self(n - 1) + self(n - 2) self.cache.append(fib_number) return self.cache[n]

Aqui está um resumo do que está acontecendo no código:

A Linha 3 define a classe Fibonacci.

A Linha 4 define o inicializador da classe, .__init__(). É um método especial que você pode usar para inicializar suas instâncias de classe. Métodos especiais são às vezes chamados de métodos dunder, abreviação de métodos de sublinhado duplo.

A Linha 5 cria o atributo de instância .cache, o que significa que sempre que você criar um objeto Fibonacci, haverá um cache para ele. Este atributo contém inicialmente os primeiros números da sequência de Fibonacci.

A Linha 7 define outro método especial, .__call__(). Este método transforma as instâncias de Fibonacci em objetos que podem ser chamados.

As linhas 9 e 10 validam o valor de n usando uma instrução condicional. Se n não for um número inteiro positivo, então o método gera um ValueError.

A Linha 13 define uma instrução condicional para verificar os números de Fibonacci que já foram calculados e estão disponíveis em .cache. Se o número no índice n já estiver em .cache, a linha 14 o retornará. Caso contrário, a linha 17 calcula o número e a linha 18 anexa-o a .cache para que você não precise calculá-lo novamente.

A linha 20 retorna o número de Fibonacci solicitado.

Para testar este código, salve-o em fibonacci_class.py. Em seguida, execute este código em seu shell interativo:

>>> from fibonacci_class import Fibonacci >>> fibonacci_of = Fibonacci() >>> fibonacci_of(5) 5 >>> fibonacci_of(6) 8 >>> fibonacci_of(7) 13 >>> [fibonacci_of(n) for n in range(15)] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Aqui, você cria e chama uma instância da classe Fibonacci chamada fibonacci_of. A primeira chamada usa 5 como argumento e retorna 5, que é o sexto número de Fibonacci porque você está usando índices baseados em zero.

Esta implementação do algoritmo da sequência de Fibonacci é bastante eficiente. Depois de ter uma instância da classe, o atributo .cache contém os números já computados de chamada para chamada.

Visualizando o algoritmo de sequência de Fibonacci memorizado

Você pode entender efetivamente como cada chamada para uma função recursiva de Fibonacci é tratada usando uma representação de pilha de chamadas. A maneira como cada chamada é colocada na pilha e retirada reflete exatamente como o programa é executado. Isso demonstra claramente como o cálculo de números grandes levará muito tempo se você não otimizar o algoritmo.

Em uma pilha de chamadas, sempre que uma função retorna um resultado, um quadro de pilha que representa a chamada de função é retirado da pilha. Sempre que você chama uma função, você adiciona um novo quadro de pilha ao topo da pilha. Em geral, esta operação tem uma complexidade de espaço de O(n) porque não há mais do que n quadros de pilha na pilha de chamadas em um determinado momento. única vez.

Nota: existe um editor de código amigável para iniciantes chamado Thonny que permite visualizar a pilha de chamadas de uma função recursiva de forma gráfica. Você pode conferir Thonny: o editor Python para iniciantes para saber mais.

Para visualizar o algoritmo recursivo de Fibonacci memorizado, você usará um conjunto de diagramas que representam a pilha de chamadas. O número da etapa é indicado pelo rótulo azul abaixo de cada pilha de chamadas.

Digamos que você queira calcular F(5). Para fazer isso, você envia a primeira chamada da função para a pilha de chamadas:

Para calcular F(5), você deve calcular F(4) conforme descrito pela relação de recorrência de Fibonacci, então adicione essa nova chamada de função à pilha:

Para calcular F(4), você deve calcular F(3), então adicione outra chamada de função à pilha:

Para calcular F(3), você deve calcular F(2), então adicione outra chamada de função à pilha de chamadas:

Para calcular F(2), você deve calcular F(1), então adicione-o à pilha. Como F(1) é um caso base, ele retorna imediatamente com 1, e você remove esta chamada da pilha:

Agora você começa a desenrolar os resultados recursivamente. F(1) retorna o resultado para sua função de chamada, F(2). Para calcular F(2), você também precisa calcular F(0):

Você adiciona F(0) à pilha. Como F(0) é um caso base, ele retorna imediatamente, fornecendo 0. Agora você pode removê-lo da pilha de chamadas:

Este resultado da chamada de F(0) é retornado para F(2). Agora você tem o que precisa para calcular F(2) e removê-lo da pilha:

O resultado de F(2) é retornado ao seu chamador, F(3). F(3) também precisa dos resultados de F(1) para completar seu cálculo, então você o adiciona de volta à pilha:

F(1) é um caso base e seu valor está disponível no cache, então você pode retornar o resultado imediatamente e remover F(1) da pilha:

Você pode completar o cálculo para F(3), que é 2:

Você remove F(3) da pilha após completar seu cálculo e retorna o resultado para seu chamador, F(4). F(4) também precisa do resultado de F(2) para calcular seu valor:

Você coloca a chamada para F(2) na pilha. É aqui que entra o cache bacana. Você já o calculou antes, então pode simplesmente recuperar o valor do cache, evitando uma chamada recursiva para calcular o resultado de F(2) novamente. O cache retorna 1 e você remove F(2) da pilha:

F(2) é retornado ao seu chamador, e agora F(4) tem tudo o que precisa para calcular seu valor, que é 3:

Em seguida, você remove F(4) da pilha e retorna seu resultado para o chamador final e original, F(5):

F(5) agora tem o resultado de F(4) e também o resultado de F(3). Você coloca uma chamada F(3) na pilha e o cache bacana entra em ação novamente. Você calculou anteriormente F(3), então tudo que você precisa fazer é recuperá-lo do cache. Não há processo recursivo para calcular F(3). Ele retorna 2 e você remove F(3) da pilha:

Agora F(5) tem todos os valores necessários para calcular seu próprio valor. Você obtém 5 adicionando 3 e 2, e essa é a etapa final antes de retirar a chamada F(5) da pilha. Esta ação encerra sua sequência de chamadas de função recursivas:

A pilha de chamadas está vazia agora. Você concluiu a etapa final para calcular F(5):

Representar chamadas de função recursivas usando um diagrama de pilha de chamadas ajuda a entender todo o trabalho que ocorre nos bastidores. Também permite ver quantos recursos uma função recursiva pode consumir.

Reunir todos esses diagramas permite visualizar como é todo o processo:

Você pode clicar na imagem acima para ampliar as etapas individuais. Se você não armazenar em cache os números de Fibonacci calculados anteriormente, alguns dos estágios da pilha neste diagrama seriam muito mais altos, o que significa que levariam mais tempo para retornar um resultado aos seus respectivos chamadores.

Usando iteração e uma função Python

O exemplo das seções anteriores implementa uma solução recursiva que usa memoização como estratégia de otimização. Nesta seção, você codificará uma função que usa iteração. O código abaixo implementa uma versão iterativa do seu algoritmo de sequência de Fibonacci:

# fibonacci_func.py def fibonacci_of(n): # Validate the value of n if not (isinstance(n, int) and n >= 0): raise ValueError(f'Positive integer number expected, got "{n}"') # Handle the base cases if n in {0, 1}: return n previous, fib_number = 0, 1 for _ in range(2, n + 1): # Compute the next Fibonacci number, remember the previous one previous, fib_number = fib_number, previous + fib_number return fib_number

Agora, em vez de usar recursão em fibonacci_of(), você está usando iteração. Esta implementação do algoritmo de sequência de Fibonacci é executada em tempo linear O(n). Aqui está um detalhamento do código:

A Linha 3 define fibonacci_of(), que recebe um número inteiro positivo, n, como argumento.

As linhas 5 e 6 realizam a validação usual de n.

As linhas 9 e 10 tratam dos casos base onde n é 0 ou 1.

A linha 12 define duas variáveis locais, anterior e fib_number, e as inicializa com os dois primeiros números da sequência de Fibonacci.

A Linha 13 inicia um loop for que itera de 2 a n + 1. O loop usa um sublinhado (_) para a variável de loop porque é uma variável descartável e você não usará esse valor no código.

A Linha 15 calcula o próximo número de Fibonacci na sequência e lembra o anterior.

A linha 17 retorna o número de Fibonacci solicitado.

Para testar esse código, volte para sua sessão interativa e execute o seguinte código:

>>> from fibonacci_func import fibonacci_of >>> fibonacci_of(5) 5 >>> fibonacci_of(6) 8 >>> fibonacci_of(7) 13 >>> [fibonacci_of(n) for n in range(15)] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Esta implementação de fibonacci_of() é mínima. Ele usa descompactação iterável para calcular os números de Fibonacci durante os loops, o que é bastante eficiente em termos de memória. No entanto, toda vez que você chama a função com um valor diferente de n, ela precisa recalcular a sequência novamente. Para corrigir isso, você pode usar encerramentos e fazer sua função lembrar os valores já calculados entre as chamadas. Vá em frente e experimente!

Conclusão

A sequência de Fibonacci pode ajudá-lo a melhorar sua compreensão da recursão. Neste tutorial, você aprendeu o que é a sequência de Fibonacci. Você também aprendeu sobre alguns algoritmos comuns para gerar a sequência e como traduzi-los em código Python.

A sequência de Fibonacci pode ser um excelente trampolim e ponto de entrada no mundo da recursão, que é uma habilidade fundamental para se ter como programador.

Neste tutorial, você aprendeu como:

Gere a sequência de Fibonacci usando um algoritmo recursivo

Otimize seu algoritmo recursivo de Fibonacci usando memoização

Gere a sequência de Fibonacci usando um algoritmo iterativo

Você também visualizou o algoritmo recursivo memorizado para entender melhor como ele funciona nos bastidores. Para fazer isso, você usou um diagrama de pilha de chamadas.

Depois de dominar os conceitos deste tutorial, suas habilidades de programação em Python irão melhorar junto com seu pensamento algorítmico recursivo.