Langage de programmation - Mathématiques appliquées

Les nombres de Fibonacci

Les nombres de Fibonacci forment une suite d'entiers dans laquelle chaque terme est obtenu en additionnant les deux termes qui le précèdent. Cette suite constitue l'un des exemples les plus connus de définition récursive et occupe une place importante en mathématiques appliquées, en algorithmique, en combinatoire, en théorie des nombres et en programmation.

En informatique, la suite de Fibonacci est souvent utilisée pour expliquer la récursivité, la programmation dynamique, la mémorisation, l'analyse de complexité et les méthodes de calcul matriciel. Elle permet de comparer plusieurs approches produisant le même résultat, mais dont les performances peuvent être radicalement différentes.

Les nombres de Fibonacci apparaissent également dans des problèmes de dénombrement, dans l'étude des structures arborescentes, dans certaines méthodes de recherche et dans des structures de données comme les tas de Fibonacci. Leur relation avec le nombre d'or, les coefficients binomiaux et les fonctions génératrices en fait une notion centrale des fondements mathématiques de la programmation.

Historique

La suite porte le nom de Leonardo de Pise, plus connu sous le nom de Fibonacci, un mathématicien italien ayant vécu aux XII^e et XIII^e siècles. Il la présenta en Europe dans son ouvrage Liber Abaci, publié en 1202, à travers un problème théorique portant sur la reproduction d'une population de lapins.

Cependant, des suites équivalentes étaient connues bien avant Fibonacci, notamment dans les mathématiques indiennes, où elles apparaissaient dans l'étude des rythmes et des combinaisons de syllabes longues et courtes.

Le mérite de Fibonacci réside principalement dans la diffusion de cette suite dans les mathématiques européennes. Depuis, elle est devenue un exemple classique dans l'enseignement de l'algorithmique et de la récursivité.

Définition

La suite de Fibonacci est généralement définie par :

F₀ = 0
F₁ = 1

et, pour tout entier :

n ≥ 2

par la relation :

F_n = F_n-1 + F_n-2

Chaque terme est donc égal à la somme des deux termes précédents.

Les premiers nombres de Fibonacci sont :

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Convention commençant par 1

Certaines documentations présentent la suite sous la forme :

1, 1, 2, 3, 5, 8, 13, 21, ...

Cette convention utilise généralement :

F₁ = 1
F₂ = 1

Elle décrit la même suite, mais avec des indices décalés.

En programmation, il est important de préciser la convention utilisée, car :

F₀ = 0

dans la définition moderne la plus courante, tandis que certaines bibliothèques ou certains exercices commencent directement à :

F₁ = 1

Construction de la suite

Les premiers termes sont obtenus comme suit :

F₀ = 0
F₁ = 1

Puis :

F₂ = F₁ + F₀
   = 1 + 0
   = 1
F₃ = F₂ + F₁
   = 1 + 1
   = 2
F₄ = F₃ + F₂
   = 2 + 1
   = 3
F₅ = F₄ + F₃
   = 3 + 2
   = 5
F₆ = F₅ + F₄
   = 5 + 3
   = 8

Le même principe est appliqué pour produire tous les termes suivants.

Premières valeurs

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
15	610
20	6 765
30	832 040
40	102 334 155
50	12 586 269 025

La croissance des nombres de Fibonacci est rapide, bien qu'elle soit moins importante que celle de la fonction factorielle.

Définition récursive

La définition mathématique de la suite se traduit directement par un algorithme récursif.

MODULE Fibonacci(n)

   SI n = 0 ALORS
      RETOURNER 0
   FIN SI

   SI n = 1 ALORS
      RETOURNER 1
   FIN SI

   RETOURNER
      Fibonacci(n - 1)
      +
      Fibonacci(n - 2)

Cet algorithme est très simple et reproduit exactement la définition mathématique.

Cependant, il est extrêmement inefficace pour les grandes valeurs de n.

Arbre des appels récursifs

Pour calculer :

Fibonacci(5)

l'algorithme calcule :

Fibonacci(4) + Fibonacci(3)

Puis :

Fibonacci(4)

demande :

Fibonacci(3) + Fibonacci(2)

et :

Fibonacci(3)

est à nouveau recalculé dans une autre branche.

Une représentation simplifiée est :

Plusieurs valeurs sont donc calculées de nombreuses fois.

Complexité de la récursion naïve

L'algorithme récursif naïf produit un nombre d'appels qui augmente exponentiellement.

Sa complexité temporelle est souvent exprimée par :

O(2ⁿ)

Une estimation plus précise est :

O(φⁿ)

où φ représente le nombre d'or.

La profondeur maximale de récursion est proportionnelle à :

La complexité mémoire liée à la pile d'appels est donc :

O(n)

Cette méthode est principalement utile pour illustrer la récursivité, mais elle ne devrait pas être utilisée pour des calculs importants.

Algorithme itératif

Une méthode beaucoup plus efficace consiste à calculer les termes successivement en conservant uniquement les deux valeurs précédentes.

MODULE Fibonacci(n)

   SI n = 0 ALORS
      RETOURNER 0
   FIN SI

   précédent ← 0
   courant ← 1

   BOUCLE POUR i ← 2 JUSQU'A n
      suivant ← précédent + courant
      précédent ← courant
      courant ← suivant
   FIN BOUCLE POUR
   RETOURNER courant

Cette méthode évite les calculs répétés.

Exemple d'exécution

Pour calculer :

F₆

les variables évoluent ainsi :

Itération	précédent	courant	suivant
Initialisation	0	1	-
2	1	1	1
3	1	2	2
4	2	3	3
5	3	5	5
6	5	8	8

Le résultat final est :

F₆ = 8

Complexité de la méthode itérative

La boucle effectue approximativement n itérations.

La complexité temporelle est donc :

O(n)

Seules quelques variables sont utilisées, indépendamment de la valeur de n.

La complexité mémoire supplémentaire est :

O(1)

Cette méthode est simple, rapide et adaptée à la majorité des applications courantes.

Exemple en Java


public class FibonacciSample {
 
    public static long fibonacci(int n) {
        if (n < 0) {
            throw new IllegalArgumentException(
                "L'indice doit être positif ou nul."
            );
        }
 
        if (n == 0) {
            return 0;
        }
 
        long precedent = 0;
        long courant = 1;
 
        for (int i = 2; i <= n; i++) {
            long suivant = precedent + courant;
            precedent = courant;
            courant = suivant;
        }
 
        return courant;
    }
 
    public static void main(String[] args) {
        for (int i = 0; i <= 10; i++) {
            System.out.println(
                "F" + i + " = " + fibonacci(i)
            );
        }
    }
}

Le programme affiche :

F0 = 0
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55

Mémorisation

La mémorisation consiste à conserver les résultats déjà calculés afin d'éviter de les recalculer.

MODULE Fibonacci(n, mémoire)

   SI n existe dans mémoire ALORS
      RETOURNER mémoire[n]
   FIN SI

   SI n = 0 ALORS
      RETOURNER 0
   FIN SI

   SI n = 1 ALORS
      RETOURNER 1
   FIN SI

   mémoire[n] ←
      Fibonacci(n - 1, mémoire)
      +
      Fibonacci(n - 2, mémoire)

   RETOURNER mémoire[n]

Chaque valeur comprise entre 0 et n n'est calculée qu'une seule fois.

Complexité avec mémorisation

La mémorisation réduit la complexité temporelle à :

O(n)

La mémoire utilisée pour conserver les résultats et la pile récursive est :

O(n)

Cette méthode conserve la structure récursive tout en éliminant les calculs redondants.

Elle constitue un exemple classique de programmation dynamique descendante, également appelée approche top-down.

Programmation dynamique ascendante

Une autre approche consiste à remplir un tableau dans l'ordre croissant des indices.

MODULE Fibonacci(n)

   Créer tableau F[0..n]

   F[0] ← 0

   SI n ≥ 1 ALORS
      F[1] ← 1
   FIN SI

   BOUCLE POUR i ← 2 JUSQU'A n
      F[i] ← F[i - 1] + F[i - 2]
   FIN BOUCLE POUR

   RETOURNER F[n]

Cette méthode est appelée programmation dynamique ascendante, ou bottom-up.

Sa complexité temporelle est :

O(n)

et sa complexité mémoire est :

O(n)

Elle est utile lorsque plusieurs termes de la suite doivent être conservés ou réutilisés.

Calcul matriciel

La relation de Fibonacci peut être exprimée à l'aide de matrices :

| F_n+1 | | 1 1 | | F_n |
| F_n | = | 1 0 | | F_n-1 |

On peut donc écrire :

| F_n+1  F_n   |
| F_n    F_n-1 |
=
| 1  1 |_n
| 1  0 |

Le calcul de la puissance de cette matrice par exponentiation rapide permet d'obtenir F? en un nombre logarithmique d'étapes.

Exponentiation rapide de matrices

L'exponentiation rapide repose sur les propriétés suivantes :

Mⁿ = (M^n/2)²

lorsque n est pair, et :

Mⁿ = M × M^n-1

lorsque n est impair.

Le nombre d'étapes nécessaires est proportionnel à :

log n

La complexité temporelle du calcul matriciel est donc :

O(log n)

si l'on considère les opérations arithmétiques élémentaires comme ayant un coût constant.

Méthode du doublement rapide

La méthode du doublement rapide, ou fast doubling, permet de calculer directement deux termes consécutifs.

Elle repose sur les identités :

F_2k = F_k × (2F_k+1 - F_k)

et :

F_2k+1 = F_k² + F_k+1²

Ces identités permettent de diviser l'indice par deux à chaque étape.

Algorithme du doublement rapide

MODULE FibonacciDoublement(n)

   SI n = 0 ALORS
      RETOURNER (0,1)
   FIN SI

   (a,b) ← FibonacciDoublement(n DIV 2)

   c ← a × (2 × b - a)
   d ← a × a + b × b

   SI n est pair ALORS
      RETOURNER (c,d)
   SINON
      RETOURNER (d,c+d)
   FIN SI

La paire retournée contient :

(F_n,F_n+1)

La complexité temporelle est :

O(log n)

Cette méthode est généralement plus simple et plus efficace que la multiplication de matrices complète.

Exemple en Java avec BigInteger


import java.math.BigInteger;
 
public class FibonacciRapideSample {
 
    public static BigInteger[] fibonacci(
        long n
    ) {
        if (n == 0) {
            return new BigInteger[] {
                BigInteger.ZERO,
                BigInteger.ONE
            };
        }
 
        BigInteger[] paire =
            fibonacci(n / 2);
 
        BigInteger a = paire[0];
        BigInteger b = paire[1];
 
        BigInteger c = a.multiply(
            b.shiftLeft(1).subtract(a)
        );
 
        BigInteger d = a.multiply(a)
            .add(b.multiply(b));
 
        if (n % 2 == 0) {
            return new BigInteger[] {c, d};
        }
 
        return new BigInteger[] {
            d,
            c.add(d)
        };
    }
 
    public static void main(String[] args) {
        System.out.println(
            "F100 = " + fibonacci(100)[0]
        );
    }
}

Le programme affiche :

F100 = 354224848179261915075

L'utilisation de BigInteger permet de calculer des termes dépassant la capacité des entiers de 64 bits.

Formule de Binet

Le nombre de Fibonacci d'indice n peut également être calculé par une formule fermée appelée formule de Binet :

F_n =
(φⁿ - ψⁿ) / √5

où :

F_n =
ψ = (1 + √5) / 2

et :

Ψ = (1 - √5) / 2

Le nombre Φ est appelé nombre d'or.

Comme la valeur absolue de Ψ est inférieure à 1, le terme Ψⁿ devient très petit lorsque n augmente.

Approximation avec le nombre d'or

Pour les valeurs suffisamment grandes de n, on peut écrire :

F_n ≈ φⁿ / √5

Le terme exact peut être obtenu en arrondissant cette valeur à l'entier le plus proche :

F_n =
Arrondi(Φⁿ / √5)

Cette relation montre que la croissance de la suite est essentiellement exponentielle.

En notation asymptotique :

F_n = Θ(φⁿ)

Limites de la formule de Binet

La formule de Binet paraît permettre un calcul en temps constant. Toutefois, son utilisation avec des nombres à virgule flottante présente plusieurs limites :

les puissances deviennent rapidement très grandes ;
les erreurs d'arrondi augmentent avec n ;
la représentation flottante ne conserve pas tous les chiffres ;
le résultat peut devenir incorrect pour de grands indices ;
le coût réel du calcul de grandes puissances n'est pas nécessairement constant.

Cette formule est donc surtout utile pour les démonstrations, les approximations et l'étude de la croissance de la suite.

Relation avec le nombre d'or

Le rapport de deux termes consécutifs tend vers le nombre d'or :

F_n+1 / F_n → φ

lorsque :

n → ∞

Quelques rapports sont :

F₅ / F₄ = 5 / 3 ≈ 1,666667
F₁₀ / F₉ = 55 / 34 ≈ 1,617647
F₂₀ / F₁₉ =
6765 / 4181
≈ 1,618034

La valeur du nombre d'or est approximativement :

φ ≈ 1,6180339887

Propriétés de divisibilité

Les nombres de Fibonacci possèdent plusieurs propriétés arithmétiques remarquables.

Si m divise n, alors :

F_m divise F_n

Par exemple :

4 divise 8

et :

F₄ = 3

divise :

F₈ = 21

De plus :

PGCD(F_m,F_n) =
FPGCD(m,n)

Par exemple :

PGCD(F₈,F₁₂)
=
F₄
=
3

car :

PGCD(8,12) = 4

Identité de Cassini

L'identité de Cassini établit que :

F_n+1F_n-1 - F_n² = (-1)ⁿ

Par exemple, pour :

n = 5

on obtient :

F₆F₄ - F₅²

soit :

8 × 3 - 5²

donc :

24 - 25 = -1

Comme 5 est impair :

(-1)⁵ = -1

L'identité est donc vérifiée.

Somme des nombres de Fibonacci

La somme des termes de F₀ à F_n est :

∑_i=0ⁿ F_i =
F_n+2 - 1

Par exemple :

F₀ + F₁ + F₂ + F₃ + F₄ + F₅

donne :

0 + 1 + 1 + 2 + 3 + 5 = 12

Or :

F₇ - 1 = 13 - 1 = 12

Somme des carrés

La somme des carrés des premiers termes satisfait :

∑_i=0ⁿ F_i² =
F_nF_n+1

Par exemple, pour :

n = 5

on obtient :

0² + 1² + 1² + 2² + 3² + 5²

soit :

0 + 1 + 1 + 4 + 9 + 25 = 40

Et :

F₅F₆ = 5 × 8 = 40

Relation avec les coefficients binomiaux

Les nombres de Fibonacci peuvent être exprimés à l'aide de coefficients binomiaux :

F_n =
∑_k=0⌊(n-1)/2⌋
C(n-k-1,k)

Par exemple, pour :

n = 6

on obtient :

F₆ =
C(5,0) + C(4,1) + C(3,2)

soit :

1 + 4 + 3 = 8

Cette identité montre le lien entre la suite de Fibonacci et les problèmes de dénombrement.

Interprétation combinatoire

Les nombres de Fibonacci peuvent compter le nombre de façons de parcourir une distance avec des pas de longueur 1 ou 2.

Supposons qu'un escalier contient n marches et qu'une personne peut monter :

une marche à la fois ;
deux marches à la fois.

Le nombre de façons d'atteindre la marche n satisfait :

M(n) = M(n-1) + M(n-2)

car le dernier déplacement est nécessairement :

un pas de 1 depuis la marche n-1 ;
ou un pas de 2 depuis la marche n-2.

Cette relation est identique à celle de Fibonacci.

Exemple de l'escalier

Pour un escalier de quatre marches, les parcours possibles sont :

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2

Il existe donc 5 possibilités.

Avec la convention appropriée :

M(4) = F₅ = 5

Ce type de problème constitue un exemple classique de programmation dynamique.

Pavages d'une bande

Les nombres de Fibonacci comptent également le nombre de façons de recouvrir une bande de longueur n avec :

des carrés de longueur 1 ;
des dominos de longueur 2.

Le dernier élément du pavage est soit :

un carré, laissant une bande de longueur n-1 ;
un domino, laissant une bande de longueur n-2.

Le nombre de pavages satisfait donc la même relation de récurrence.

Chaînes binaires sans deux 1 consécutifs

Le nombre de chaînes binaires de longueur n ne contenant pas deux bits 1 consécutifs est lié aux nombres de Fibonacci.

Par exemple, pour une longueur de 3, les chaînes autorisées sont :

000
001
010
100
101

Il existe cinq chaînes.

Ce nombre correspond à :

F₅ = 5

De manière générale, le nombre de chaînes binaires de longueur n sans deux 1 consécutifs est :

F_{n + 2}

Recherche de Fibonacci

La recherche de Fibonacci est une méthode permettant de rechercher une valeur dans un tableau trié.

Elle divise le tableau à l'aide de nombres de Fibonacci plutôt qu'en utilisant directement le milieu comme la recherche binaire.

Son principe consiste à comparer la valeur recherchée avec un élément situé à une position déterminée par un nombre de Fibonacci, puis à réduire progressivement l'intervalle de recherche.

Sa complexité temporelle est :

O(log n)

Elle peut être utile lorsque l'accès séquentiel est moins coûteux que certains accès aléatoires, bien que la recherche binaire soit généralement plus courante.

Tas de Fibonacci

Un tas de Fibonacci est une structure de données composée d'une collection d'arbres respectant une propriété de tas.

Cette structure permet notamment :

l'insertion en temps amorti constant ;
la fusion en temps amorti constant ;
la diminution d'une clé en temps amorti constant ;
l'extraction du minimum en temps logarithmique amorti.

Les tas de Fibonacci sont utilisés dans certains algorithmes de graphes, notamment les variantes théoriquement optimisées de l'algorithme de Dijkstra et de l'algorithme de Prim.

Leur nom vient de l'utilisation des nombres de Fibonacci dans l'analyse de la taille minimale des arbres qu'ils contiennent.

Suite modulo un entier

Lorsqu'on calcule les nombres de Fibonacci modulo un entier m, les valeurs finissent par se répéter périodiquement.

La suite :

F_n MOD m

possède une période appelée période de Pisano.

Par exemple, modulo 2, la suite devient :

0, 1, 1, 0, 1, 1, 0, ...

Sa période est donc :

Cette propriété est utile dans les calculs modulaires portant sur de très grands indices.

Dépassement de capacité

Les nombres de Fibonacci croissent rapidement.

Pour un entier signé de 32 bits, la plus grande valeur représentable de la suite est :

F₄₆ = 1836311903

Le terme suivant :

F₄₇ = 2971215073

dépasse la capacité maximale d'un entier signé de 32 bits.

Pour un entier signé de 64 bits, la plus grande valeur représentable est :

F₉₂ =
7540113804746346429

Le terme :

F₉₃ =
12200160415121876738

dépasse cette capacité.

Pour les indices supérieurs, il faut utiliser des entiers multiprécision.

Nombres négatifs

La suite peut être étendue aux indices négatifs.

Ces valeurs sont appelées nombres de Fibonacci négatifs ou négafibonacci.

La relation est :

F_-n = (-1)ⁿ⁺¹F_n

Par exemple :

F_-1 = 1
F_-2 = -1
F_-3 = 2
F_-4 = -3
F_-5 = 5

Les signes alternent, tandis que les valeurs absolues restent celles de la suite ordinaire.

Fonction génératrice

La fonction génératrice ordinaire de la suite de Fibonacci est :

G(x) =
F₀ + F₁x + F₂x² + F₃x³ + ...

Elle est donnée par :

G(x) = x / (1 - x - x²)

Cette expression permet d'étudier algébriquement la suite, de retrouver sa relation de récurrence et de démontrer plusieurs identités.

Les fonctions génératrices seront abordées plus en détail dans une section distincte.

Comparaison des méthodes de calcul

Méthode	Temps	Mémoire	Caractéristique
Récursion naïve	O(φⁿ)	O(n)	Simple, mais très lente
Récursion mémorisée	O(n)	O(n)	Conserve la récursivité
Programmation dynamique	O(n)	O(n)	Conserve tous les termes
Méthode itérative	O(n)	O(1)	Simple et efficace
Calcul matriciel	O(log n)	O(log n) ou O(1)	Adapté aux grands indices
Doublement rapide	O(log n)	O(log n)	Très efficace
Formule de Binet	Théoriquement courte	O(1)	Risques d'arrondi

Pour les calculs exacts de grands nombres de Fibonacci, la méthode du doublement rapide associée à des entiers multiprécision constitue généralement un excellent choix.

Complexité arithmétique réelle

Lorsque les valeurs deviennent très grandes, une addition n'a plus un coût constant.

Le nombre de bits de F_n est proportionnel à :

car :

F_n ≈ φⁿ / √5

Les opérations sur ces grands entiers deviennent donc progressivement plus coûteuses.

Ainsi, les complexités comme :

O(n)

ou :

O(log n)

comptent généralement le nombre d'opérations arithmétiques, mais ne représentent pas toujours le coût exact de la manipulation de nombres multiprécision.

Applications

Les nombres de Fibonacci sont utilisés dans de nombreux domaines :

enseignement de la récursivité ;
programmation dynamique ;
analyse de complexité ;
dénombrement ;
combinatoire ;
théorie des nombres ;
calcul matriciel ;
algorithmes de recherche ;
structures de données ;
algorithmes de graphes ;
génération de suites ;
calcul modulaire ;
modélisation de certains phénomènes de croissance ;
étude des fonctions génératrices.

Ils servent également d'exemple pour comparer différentes stratégies algorithmiques.

Avantages

Les nombres de Fibonacci présentent plusieurs avantages pédagogiques et pratiques :

leur définition récursive est simple ;
ils permettent d'illustrer les calculs redondants ;
ils montrent l'intérêt de la programmation dynamique ;
ils permettent de comparer plusieurs complexités ;
ils possèdent de nombreuses identités mathématiques ;
ils sont liés au nombre d'or ;
ils apparaissent dans plusieurs problèmes de dénombrement ;
ils peuvent être calculés efficacement pour de très grands indices.

Limites et précautions

Plusieurs précautions doivent être prises :

la convention d'indexation doit être clairement définie ;
la récursion naïve devient rapidement inutilisable ;
les valeurs dépassent rapidement les types numériques standards ;
la formule de Binet peut produire des erreurs d'arrondi ;
la récursion profonde peut provoquer un dépassement de pile ;
le coût des grands entiers doit être pris en compte ;
les nombres de Fibonacci ne doivent pas être interprétés comme une description universelle des formes naturelles ;
les calculs modulaires exigent parfois l'étude de la période de Pisano.

Remarque

Les nombres de Fibonacci constituent un exemple particulièrement riche de relation entre une définition mathématique simple et des problèmes algorithmiques complexes. Une implémentation récursive directe peut nécessiter un temps exponentiel, tandis qu'une méthode itérative réduit ce coût à un temps linéaire et que le doublement rapide permet d'atteindre un temps logarithmique en nombre d'étapes. Cette différence illustre l'importance du choix de l'algorithme, même lorsque la formule mathématique de départ paraît élémentaire.

La suite relie également la récursivité, la programmation dynamique, le nombre d'or, les coefficients binomiaux, le calcul matriciel et les fonctions génératrices. Elle constitue ainsi une excellente transition vers l'étude des fonctions génératrices, lesquelles permettent de représenter et d'analyser des suites numériques à l'aide de séries formelles.

Dernière mise à jour : Jeudi, le 16 juillet 2026