Séquence de Fibonacci en Python

La suite de Fibonacci commence par F0 = 0 et F1 = 1. Chaque terme suivant est la somme des deux précédents : Fn = Fn-1 + Fn-2. Avec une numérotation à partir de zéro, ses premiers termes sont 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233. Pour générer une suite, déterminez si votre entrée désigne un nombre de termes ou un indice ; sauf indication contraire, les exemples ci-dessous utilisent un nombre de termes.

Générer une suite de Fibonacci avec une boucle

Une boucle est le choix pratique par défaut lorsque vous avez besoin des n premiers termes. Elle s’exécute en O(n) et ne conserve que les deux valeurs précédentes comme état auxiliaire. La liste renvoyée occupe à elle seule un espace de sortie de O(n) ; pour n = 1, elle contient [0].

Exécutez cet exemple :

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

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]

À chaque itération, la valeur courante est ajoutée à la liste avant la mise à jour de la paire. Cet ordre conserve F0 comme premier élément et fait correspondre la longueur demandée à celle de la liste. Python entiers peuvent dépasser la taille des entiers machine à largeur fixe : les termes restent donc exacts, même lorsqu’ils deviennent très grands, bien que les opérations arithmétiques prennent plus de temps à mesure que les nombres grandissent.

Calculer des nombres de Fibonacci par récursion

La récursion directe reproduit la définition : pour calculer Fn, la fonction s’appelle elle-même pour Fn-1 et Fn-2. La version simple ci-dessous permet de comprendre le fonctionnement de la récurrence, mais elle répète de nombreux calculs. Son temps d’exécution croît de façon exponentielle, et les appels profonds utilisent également la pile d’appels de l’interpréteur. Elle accepte uniquement les indices de la suite standard, à partir de 0, et lève ValueError pour un indice inférieur à 0. Pour les indices plus grands, préférez une boucle ou le stockage des résultats.

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

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)])

Ici, l’argument est un indice, et non un nombre de termes : la compréhension de liste demande les valeurs de F0 à F9. Les cas de base renvoient directement les valeurs de départ.

Construire une suite de Fibonacci avec la programmation dynamique

La programmation dynamique stocke les résultats afin que chaque terme ne soit calculé qu’une fois. Pour n <= 0, elle renvoie [] ; sinon, cette version fondée sur une liste s’exécute en O(n) et utilise un espace total de O(n), liste renvoyée comprise. La boucle ci-dessus utilise elle aussi un espace total de O(n) lorsqu’elle renvoie une liste, mais ne nécessite qu’un espace auxiliaire de O(1) en plus de cette sortie. Si vous avez seulement besoin du terme final, un calcul itératif avec deux variables peut utiliser un espace total de O(1).

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

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]

La mise à jour suit la même récurrence que la boucle, tandis que la liste conserve les valeurs précédentes. Choisissez cette méthode si vous devez accéder aux termes antérieurs de la suite lors d’étapes ultérieures. Optez pour la boucle qui renvoie une liste si vous souhaitez générer la suite simplement, avec un état auxiliaire constant ; la liste renvoyée occupe tout de même un espace de O(n). Si vous n’avez besoin que d’une valeur à un indice donné, une boucle à deux variables évite de stocker toute la suite.

Calculer des nombres de Fibonacci avec la formule de Binet

La formule de Binet exprime directement les nombres de Fibonacci selon une numérotation à partir de zéro, à l’aide de puissances et du nombre d’or φ = (1 + √5) / 2 :

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

Une implémentation directe en Python peut utiliser math.sqrt, mais les calculs en virgule flottante n’offrent qu’une approximation des valeurs irrationnelles. Pour des indices suffisamment grands, les arrondis peuvent donc produire un résultat décalé d’une unité. Cette formule est utile pour comprendre une forme fermée ou estimer une valeur ; pour obtenir des entiers exacts, préférez la boucle ou la programmation dynamique.

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

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]