Sequência de Fibonacci em Python

A sequência de Fibonacci começa com F0 = 0 e F1 = 1. Cada termo seguinte é a soma dos dois anteriores: Fn = Fn-1 + Fn-2. Com indexação começando em zero, os primeiros termos são 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233. Para gerar uma sequência, determine se a entrada representa a quantidade de termos ou um índice; salvo indicação em contrário, os exemplos abaixo usam a quantidade de termos.

Gere uma sequência de Fibonacci com um loop

Um loop é a opção prática padrão quando você precisa dos primeiros n termos. Ele leva O(n) tempo e mantém apenas os dois valores anteriores como estado auxiliar. A lista retornada ocupa O(n) de espaço de saída; para n = 1, ela contém [0].

Execute este exemplo. O código e os rótulos ou resultados exibidos nesta seção permanecem em inglês:

def fibonacci_sequence(n):
    terms = []
    a, b = 0, 1
    for _ in range(max(0, n)):
        terms.append(a)
        a, b = b, a + b
    return terms


print(fibonacci_sequence(10))

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

A cada iteração, o valor atual é acrescentado antes de avançar o par. Essa ordem mantém F0 como o primeiro elemento e faz com que o comprimento solicitado corresponda ao tamanho da lista. Python pode ultrapassar os limites dos inteiros de largura fixa das máquinas, portanto os termos continuam exatos mesmo quando ficam grandes, embora as operações aritméticas demorem mais à medida que os números crescem.

Calcule números de Fibonacci com recursão

A recursão direta segue a definição: para calcular Fn, a função chama a si mesma para obter Fn-1 e Fn-2. A versão simples abaixo ajuda a entender como a recorrência funciona, mas repete muitos cálculos. Seu tempo de execução cresce exponencialmente, e chamadas profundas também ocupam a pilha de chamadas do interpretador. Ela aceita apenas índices da sequência padrão, começando em 0, e gera ValueError para índices menores que 0. Para índices maiores, use um loop ou armazene os resultados. O código e os rótulos ou resultados exibidos nesta seção permanecem em inglês.

def fibonacci_recursive(n):
    if n < 0:
        raise ValueError("n must be a nonnegative index")
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)


print([fibonacci_recursive(i) for i in range(10)])

Aqui o argumento é um índice, não a quantidade de termos: a compreensão de lista solicita F0 até F9. Os casos-base retornam diretamente os valores iniciais.

Construa uma sequência de Fibonacci com programação dinâmica

A programação dinâmica armazena resultados para que cada termo seja calculado uma única vez. Para n <= 0, retorna []; caso contrário, esta versão baseada em lista leva O(n) tempo e ocupa O(n) de espaço total, incluindo a lista retornada. O loop anterior também ocupa O(n) de espaço total quando retorna uma lista, mas usa apenas O(1) de espaço auxiliar além dessa saída. Se você precisar apenas do termo final, um cálculo iterativo com duas variáveis pode usar O(1) de espaço total. O código e os rótulos ou resultados exibidos nesta seção permanecem em inglês.

def fibonacci_dynamic(n):
    if n <= 0:
        return []
    if n == 1:
        return [0]

    terms = [0, 1]
    for i in range(2, n):
        terms.append(terms[i - 1] + terms[i - 2])
    return terms


print(fibonacci_dynamic(10))

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

A atualização usa a mesma recorrência do loop, enquanto a lista registra os valores anteriores. Escolha essa abordagem quando etapas posteriores precisarem acessar termos anteriores da sequência completa. Prefira o loop que retorna uma lista quando quiser uma geração simples com estado auxiliar constante; a lista retornada ainda ocupa O(n) de espaço. Se precisar de apenas um valor em determinado índice, um loop com duas variáveis pode evitar o armazenamento da sequência.

Calcule números de Fibonacci com a fórmula de Binet

A fórmula de Binet expressa diretamente o número de Fibonacci com índice começando em zero, usando potências e a razão áurea φ = (1 + √5) / 2:

Fn = (φⁿ - ((1 - √5) / 2)ⁿ) / √5

Uma implementação direta em Python pode usar math.sqrt, mas a aritmética de ponto flutuante aproxima os valores irracionais. Por isso, para índices suficientemente grandes, o arredondamento pode produzir um resultado com diferença de uma unidade. A fórmula é útil para compreender uma forma fechada ou estimar um valor; para obter resultados inteiros exatos, prefira o loop ou a programação dinâmica. O código e os rótulos ou resultados exibidos nesta seção permanecem em inglês.

from math import sqrt


def fibonacci_binet(n):
    phi = (1 + sqrt(5)) / 2
    psi = (1 - sqrt(5)) / 2
    return round((phi ** n - psi ** n) / sqrt(5))


print([fibonacci_binet(i) for i in range(10)])

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]