Exercice 42 / 100

Récursivité - Fibonacci

ConsigneSuite de Fibonacci jusqu'à n termes

📖 Cours

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

F(0) = 0F(1) = 1F(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 plus de 330 millions d'appels (chaque appel recalcule les mêmes sous-problèmes), et ce nombre est encore multiplié par environ 1,6 à chaque n de plus. 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).