Tema

A Sequência de Fibonacci

A sequência de Fibonacci é uma sequência cujos primeiros valores são 0 e 1, e todos os números seguintes são a soma dos dois números anteriores. Então para encontrar o terceiro número da sequência, basta somar o segundo número (1) com o primeiro número (0).

0+1=1

Repetindo o padrão acima, é possível calcular os próximos números da sequência:

1+1=2
1+2=3
2+3=5
3+5=8

No geral, ela segue a seguinte regra:

$$ Fibonacci(n) = \left\{ \begin{array}\\ 0 & \mbox{se } \ n=0 \\ 1 & \mbox{se } \ n=1 \\ Fibonacci(n-1)+Fibonacci(n-2) & \mbox{se } \ n>1 \\ \end{array} \right. $$

Seguindo a definição, é possível encontrar todos os valores da sequência:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181...

Programando a sequência em Python

1 - Criando a Funcão

Começaremos definindo a função:

def fibonacci(n):

Para criar a função de modo recursivo, é necessário um caso base. Note na definição que se n==0, o resultado será 0, e se n==1, o resultado será 1. Ou seja, para todo caso onde n<=1, o resultado será o próprio n. Este será o nosso caso base, que pode ser implementado da seguinte maneira:

if n<=1:
        return n

Entretanto, o programa só irá alcançar essa parte do código caso a primeira condição seja falsa, já que a função retornará n caso n<=1. Por isso, não é necessário checar se n>1, basta manter esta parte do código no final da função.

Com isso, o resultado final da função é o seguinte:

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

2 - Chamando a Funcão

Agora, é necessário escrever um código que chame a função. Podemos imprimir um único número qualquer da sequência, ou então imprimir os x primeiros números.

Obtendo um Único Valor

Caso precisemos apenas um único número na posição n, basta imprimir a função, trocando n pela posição desejada. Para imprimir o número na posição 6, por exemplo, usamos a seguinte linha de código:

print(fibonacci(6))

8

Obtendo os X Primeiros Valores

A forma mais fácil de imprimir os x primeiros valores da sequência é usando um for loop, com o range sendo a quantidade de números que desejar:

x = 20
for n in range(x):
    print(fibonacci(n), end=' ')

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 

Também é possível gerar uma lista utilizando list comprehension:

x = 20
lista_20_numeros = [fibonacci(n) for n in range(x)]
print(lista_20_numeros)

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

3 - Código Completo

Por fim, obtemos o seguinte código:

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

x = 20
lista_20_numeros = [fibonacci(n) for n in range(x)]

print(lista_20_numeros)

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]