La suite de Fibonacci est un bon prétexte pour parler d’algorithmes sans se perdre dans une théorie inutilement lourde. On y trouve une règle simple, une convention de départ à clarifier et, surtout, un excellent exemple pour comparer récursion, boucle et programmation dynamique. Je vais aller droit au but: définition utile, méthodes de calcul, comparaison des approches et erreurs à éviter quand on l’implémente en pratique.
Les points essentiels à retenir avant de coder
- Chaque terme est la somme des deux précédents, avec une convention courante qui commence à 0 et 1.
- La version récursive est la plus élégante, mais aussi la moins efficace sans optimisation.
- Pour un usage concret, l’approche itérative est généralement la meilleure: simple, rapide et économe en mémoire.
- Au-delà de F(92), un entier signé 64 bits déborde; il faut alors un type arbitraire ou une bibliothèque big integer.
- La suite sert surtout à apprendre et à comparer des stratégies algorithmiques, pas à résoudre un besoin métier complexe.
Comprendre la suite et sa convention de départ
La suite de Fibonacci est un bon prétexte pour parler d’algorithmes sans se perdre dans une théorie inutilement lourde. La règle est connue: chaque terme est la somme des deux précédents. Avec la convention la plus courante, on obtient 0, 1, 1, 2, 3, 5, 8, 13…; avec une autre convention, certains cours démarrent à 1, 1. Le résultat visuel est le même, mais l’indexation change, et c’est exactement ce que je veux verrouiller avant d’écrire une ligne de code.
En pratique, je recommande de documenter explicitement les cas de base dans la fonction, au lieu de supposer que tout le monde partage la même notation. Si je mélange les conventions, mes tests deviennent vite trompeurs alors que le problème vient simplement du point de départ. Avec cette base posée, je peux passer aux premiers calculs concrets.
Générer les premiers termes sans se tromper
Pour générer les premiers termes, j’aime partir d’un tableau mental très simple: on garde toujours les deux derniers nombres et on calcule le suivant. C’est la logique la plus lisible, et elle évite les formules trop abstraites quand on veut juste afficher une suite ou vérifier un test unitaire.
| n | F(n) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
| 7 | 13 |
| 8 | 21 |
| 9 | 34 |
| 10 | 55 |
La boucle correspond exactement à cette idée: initialiser deux variables, les mettre à jour à chaque itération et ne conserver que ce qui est utile. Côté coût, on reste à O(n) en temps et O(1) en mémoire, ce qui est très correct pour un usage courant. Si je n’ai besoin que des valeurs jusqu’à un certain rang, je préfère presque toujours cette approche à une version plus “élégante” sur le papier.
- Je fixe les cas de base: 0 et 1.
- Je répète la mise à jour des deux dernières valeurs.
- Je décide si je veux afficher la suite entière ou seulement le terme n.
Cette mécanique suffit déjà dans la plupart des cas, mais dès qu’on commence à comparer les styles de code, les écarts de performance deviennent très visibles.
Choisir la bonne approche de calcul
Le vrai choix n’est pas “comment écrire Fibonacci”, mais “quelle version sert mon objectif”. C’est là que les différences entre récursion naïve, itération, mémoïsation et techniques plus avancées deviennent utiles. La mémoïsation, pour le dire simplement, consiste à garder en cache les résultats déjà calculés; c’est une porte d’entrée directe vers la programmation dynamique.
| Méthode | Temps | Mémoire | Ce que j’en pense |
|---|---|---|---|
| Récursive naïve | O(2^n) | O(n) | Jolie pour expliquer la récursion, mauvaise dès que n grandit. |
| Itérative | O(n) | O(1) | Mon choix par défaut pour produire une valeur ou une suite. |
| Mémoïsée | O(n) | O(n) | Bonne pour illustrer la programmation dynamique et éviter les recalculs. |
| Fast doubling ou matrice | O(log n) | Variable | Utile pour les très grands n, mais trop technique pour un premier exemple. |
Voici la version que je retiens le plus souvent en Python:
def fibonacci(n):
if n < 0:
raise ValueError("n doit être positif")
if n == 0:
return 0
a, b = 0, 1
for _ in range(1, n):
a, b = b, a + b
return bEt si je veux montrer la mémoïsation sans complexifier le raisonnement, je préfère une version cachée par décorateur:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n < 2:
return n
return fib_memo(n - 1) + fib_memo(n - 2)La première sert mieux la production, la seconde sert mieux l’apprentissage. En JavaScript, je pense aussi à passer en BigInt dès que la valeur peut dépasser la zone des entiers sûrs, sinon le résultat devient faux sans que l’erreur soit visible tout de suite. Même avec la bonne méthode, il reste pourtant quelques pièges classiques à surveiller.
Les erreurs qui faussent le résultat ou la performance
Les erreurs que je vois le plus souvent ne viennent pas de la formule elle-même, mais de l’implémentation. Elles sont banales, pourtant elles coûtent du temps parce qu’elles donnent un résultat plausible au premier coup d’œil.
- Mauvaise convention de départ : mélanger 0, 1 et 1, 1 fausse les indices et les tests.
- Récursion non optimisée : au-delà de quelques dizaines de termes, la version naïve devient vite pénible.
- Dépassement d’entier : avec un entier signé 64 bits, F(92) tient encore, mais F(93) déborde.
- Recalcul inutile : sans cache, on refait plusieurs fois le même sous-calcul.
- Confusion entre exactitude et approximation : une formule flottante peut suffire pour une estimation, mais pas pour produire des entiers exacts à grande échelle.
Pour vérifier rapidement un code, je compare toujours les premiers termes attendus avec le résultat de la fonction: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Si le début est juste, les erreurs deviennent plus faciles à isoler; une fois ce filet de sécurité en place, on peut parler du vrai intérêt de cette suite dans un projet.
Quand la suite reste utile dans un projet réel
Dans un projet réel, la suite de Fibonacci ne sert pas à “faire joli”. Je l’utilise surtout pour expliquer une idée, mesurer un algorithme ou valider une stratégie d’optimisation. C’est typiquement le genre d’exemple qui fait gagner du temps quand il faut distinguer une récursion pédagogique d’un code acceptable en production.
Le cas où je la garde
Je la garde quand je veux illustrer la différence entre récursion, mémoïsation et boucle simple. Elle est aussi utile en entretien technique, parce qu’elle révèle immédiatement si quelqu’un sait parler de complexité sans réciter des définitions vagues. Enfin, elle reste pratique pour tester un moteur de calcul, un environnement d’exécution ou une implémentation de grands entiers.
Lire aussi : Multithreading - Comprendre, maîtriser et éviter les pièges
Le cas où je m’en méfie
Je m’en méfie dès qu’on veut en faire un modèle de décision métier. La suite est trop régulière pour décrire des comportements complexes, et sa beauté mathématique la rend parfois plus séduisante qu’utile. Si votre besoin est de produire des chiffres exacts au-delà des limites natives du langage, la vraie question devient la prise en charge des entiers arbitraires, pas la suite elle-même.
Il existe bien des variantes plus mathématiques, comme la formule fermée de Binet, qui donne un calcul direct du n-ième terme, mais elle repose sur des nombres flottants et perd vite de la précision. Pour un résultat exact, lisible et robuste, je reviens presque toujours à la version itérative ou à une approche avec cache, selon le contexte.
Le choix pragmatique que je retiens
Si mon but est juste de calculer un terme ou d’afficher la suite, je prends la boucle. Si je veux montrer le principe de récursion, je garde la version naïve, mais seulement sur de petits n. Si je dois monter en gamme, je passe à la mémoïsation ou à une technique logarithmique, et je pense tout de suite au type numérique du langage.
- Usage pédagogique : récursion puis mémoïsation, pour comparer les styles.
- Usage courant : itération, parce que c’est simple et rapide.
- Gros entiers : type arbitraire ou BigInt.
- Très grands n : méthode logarithmique si le besoin est réel.
Au fond, la bonne réponse n’est pas la plus élégante en théorie, mais celle qui produit le bon résultat avec la bonne complexité et sans surprise au moment de l’exécution.
