Exercice 42 / 100

Récursivité - Fibonacci

Suite de Fibonacci jusqu'à n termes

La suite de Fibonacci : chaque terme est la somme des deux précédents.

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)   pour n ≥ 2

→ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Trois versions de Fibonacci : la récursive recalcule sans cesse les mêmes appels, la mémoisée les met en cache, l'itérative avance avec deux variables

Version récursive (DIDACTIQUE mais lente)

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

Cette version est élégante mais très lente : pour fibonacci(40), elle fait des milliards d'appels (chaque appel recalcule les mêmes sous-problèmes). Pour n > 35, ça rame.

Afficher les n premiers termes

for i in range(10):
    print(fibonacci(i), end=' ')   # 0 1 1 2 3 5 8 13 21 34

Le paramètre end=' ' empêche print() de sauter à la ligne et met un espace à la place.

Optimisation 1 : mémoisation

On met en cache les résultats déjà calculés :

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Une ligne ajoutée, et fibonacci(100) devient instantané.

Optimisation 2 : version itérative

def fibonacci(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

L'astuce a, b = b, a + b utilise le déballage de tuple pour mettre à jour les deux variables EN même temps.

Trois versions, trois leçons : récursive (simple à lire), mémoisation (récursion rapide), itérative (la plus efficace en mémoire).

exercise.py