Relations de récurrence
Les relations de récurrence constituent l'un des outils fondamentaux des mathématiques discrètes, de l'analyse des algorithmes et de l'informatique théorique. Elles permettent de définir une suite en exprimant chacun de ses termes à partir d'un ou de plusieurs termes précédents. Au lieu de disposer directement d'une formule explicite, on décrit ainsi l'évolution progressive d'une quantité.
Les relations de récurrence apparaissent naturellement dans les algorithmes récursifs, la programmation dynamique, les structures arborescentes, les graphes, les automates, les probabilités, les suites numériques, les méthodes numériques et la complexité algorithmique. Elles servent notamment à modéliser le temps d'exécution d'un algorithme, la croissance d'une population, les déplacements dans une grille, les arbres binaires ou encore les nombres de Fibonacci.
L'étude des relations de récurrence comprend leur définition, leur classification, leurs méthodes de résolution et leurs nombreuses applications pratiques en programmation.
Définition
Une relation de récurrence est une équation exprimant un terme d'une suite en fonction d'un ou de plusieurs termes précédents.
Sous sa forme générale :
| an = F(an-1,an-2,...,an-k,n) |
où :
- k représente l'ordre de la récurrence ;
- F est une fonction reliant les termes précédents ;
- des conditions initiales permettent de démarrer la suite.
Exemple simple
Considérons :
| a0 = 2 |
et :
| an = an-1 + 3 |
Les premiers termes sont :
|
2 5 8 11 14 17 ... |
Chaque terme est obtenu en ajoutant 3 au précédent.
Conditions initiales
Une relation de récurrence ne suffit généralement pas à définir complètement une suite.
Il faut également préciser les premiers termes.
Par exemple :
| an = 2an-1 |
ne permet pas de calculer :
| a1 |
si :
| a0 |
n'est pas connu.
La valeur initiale est appelée condition initiale.
Ordre d'une récurrence
L'ordre correspond au nombre maximal de termes précédents utilisés.
Exemples :
Ordre 1 :
| an = an-1 + 2 |
Ordre 2 :
| an = an-1 + an-2 |
Ordre 3 :
|
an = an-1 + an-2 + an-3 |
Plus l'ordre augmente, plus le nombre de conditions initiales nécessaires augmente.
Récurrence linéaire
Une relation est dite linéaire lorsque chaque terme apparaît au premier degré.
Par exemple :
|
an = 5an-1 - 2an-2 + 7 |
est linéaire.
En revanche :
|
an = (an-1)2 |
n'est pas linéaire.
Récurrence homogène
Une récurrence est homogène lorsque tous les termes dépendent uniquement des termes précédents.
Exemple :
|
an = 4an-1 - 3an-2 |
Il n'existe aucun terme indépendant.
Récurrence non homogène
Une récurrence non homogène comporte un terme supplémentaire.
Exemple :
|
an = 2an-1 + 5 |
Le nombre :
| 5 |
constitue le terme non homogène.
Récurrence à coefficients constants
Les coefficients sont indépendants de :
| n |
Exemple :
|
an = 3an-1 - 2an-2 |
Les coefficients :
| 3 |
et
| -2 |
restent constants.
Récurrence à coefficients variables
Les coefficients peuvent dépendre de :
| n |
Par exemple :
| an = nan-1 |
Les méthodes classiques de résolution deviennent généralement plus difficiles.
Suite arithmétique
La suite arithmétique est définie par :
|
an = an-1 + r |
où :
| r |
est la raison.
Sa solution explicite est :
|
an = a0 + nr |
Suite géométrique
Une suite géométrique vérifie :
|
an = qan-1 |
Sa solution est :
|
an = a0qn |
Suite de Fibonacci
La célèbre suite de Fibonacci est définie par :
| F0 = 0 |
| F1 = 1 |
et :
|
Fn = Fn-1 + Fn-2 |
Les premiers termes sont :
|
0 1 1 2 3 5 8 13 ... |
Cette récurrence est d'ordre 2.
Suite de Lucas
Les nombres de Lucas utilisent la même relation :
|
Ln = Ln-1 + Ln-2 |
mais avec :
| L0 = 2 |
| L1 = 1 |
Ils produisent :
|
2 1 3 4 7 11 18 ... |
Tribonacci
La suite de Tribonacci généralise Fibonacci.
Elle est définie par :
|
Tn = Tn-1 + Tn-2 + Tn-3 |
Chaque terme dépend des trois précédents.
Relation de récurrence récursive
Une fonction récursive correspond naturellement à une relation de récurrence.
Exemple :
|
MODULE Factorielle(n) SI n = 0 ALORS RETOURNER 1 FIN SI RETOURNER n × Factorielle(n-1) |
La relation correspondante est :
|
n! = n(n-1)! |
Exemple avec la somme
Considérons :
|
Sn = Sn-1 + n |
avec :
| S0 = 0 |
On obtient :
|
0 1 3 6 10 15 ... |
La solution explicite est :
|
Sn = n(n+1)/2 |
Dépliage
La méthode du dépliage consiste à remplacer successivement les termes.
Exemple :
|
an = an-1 + 2 |
Puis :
|
= (an-2+2)+2 |
Puis :
|
= an-3+6 |
En poursuivant :
|
an = a0+2n |
Méthode de substitution
Cette méthode consiste à proposer une formule explicite puis à vérifier qu'elle satisfait la récurrence.
Par exemple, supposons :
| an = 3n+5 |
On vérifie :
|
an-1+3 = 3(n-1)+5+3 = 3n+5 |
La formule est donc correcte.
Équation caractéristique
Pour les récurrences linéaires homogènes à coefficients constants, on suppose une solution :
| an = rn |
On obtient alors un polynôme appelé équation caractéristique.
Exemple :
|
an = 5an-1 - 6an-2 |
devient :
|
r2 - 5r + 6 = 0 |
Les racines sont :
| 2 |
et
| 3 |
Solution générale
Lorsque les racines sont distinctes :
| r1,r2,...,rk |
la solution est :
|
an = C1r1n + C2r2n + ... |
Les constantes sont déterminées grâce aux conditions initiales.
Racines multiples
Si une racine :
| r |
est multiple d'ordre :
| m |
la solution contient :
| rn |
multiplié par un polynôme.
Par exemple :
| (C1+C2n)rn |
pour une racine double.
Méthode des coefficients indéterminés
Pour une récurrence non homogène, on cherche une solution particulière adaptée au second membre.
Exemple :
|
an = 2an-1 + 5 |
On peut supposer :
| an = C |
La constante est ensuite déterminée par substitution.
Fonction génératrice
Les fonctions génératrices constituent une méthode puissante de résolution.
On définit :
|
A(x) = ∑anxn |
La relation de récurrence devient une équation algébrique portant sur :
| A(x) |
Cette méthode est particulièrement utilisée pour Fibonacci, Catalan et les nombres de Stirling.
Matrices
Une récurrence peut être transformée en produit matriciel.
Pour Fibonacci :
|
( Fn+1 Fn ) = ( 1 1 1 0 )^n ( 1 0 ) |
Cette représentation permet une résolution en :
| O(log n) |
grâce à l'exponentiation rapide des matrices.
Programmation dynamique
Une récurrence est souvent calculée efficacement grâce à la programmation dynamique.
Au lieu de recalculer plusieurs fois les mêmes valeurs, les résultats intermédiaires sont mémorisés.
Cette technique réduit considérablement le temps d'exécution.
Exemple de programmation dynamique
Pour Fibonacci :
| F0 ← 0 |
| F1 ← 1 |
Puis :
|
POUR i ← 2 JUSQU'A n Fi ← Fi-1 + Fi-2 FIN POUR |
Complexité :
| O(n) |
Mémoïsation
La mémoïsation consiste à conserver les résultats déjà calculés.
Exemple :
|
SI valeur existe ALORS RETOURNER valeur SINON calculer FIN SI |
Elle évite l'explosion exponentielle de certaines récursions.
Analyse d'algorithmes
Les relations de récurrence sont omniprésentes dans l'analyse des algorithmes récursifs.
Par exemple :
|
T(n) = T(n-1) + 1 |
correspond à une complexité :
| O(n) |
Recherche binaire
La recherche dichotomique satisfait :
|
T(n) = T(n/2) + 1 |
Sa solution est :
| O(log n) |
Tri fusion
Le tri fusion vérifie :
|
T(n) = 2T(n/2) + n |
Sa solution est :
| O(n log n) |
Tri rapide
En moyenne :
|
T(n) = T(k) + T(n-k-1) + n |
La complexité moyenne est :
| O(n log n) |
Le pire cas est :
| O(n2) |
Multiplication de Karatsuba
L'algorithme satisfait :
|
T(n) = 3T(n/2) + n |
La solution est :
| O(n^log23) |
Théorème maître
Le théorème maître résout automatiquement plusieurs récurrences de la forme :
|
T(n) = aT(n/b) + f(n) |
où :
- a représente le nombre de sous-problèmes ;
- b représente le facteur de réduction ;
- f(n) représente le coût hors récursion.
Il permet d'obtenir rapidement la complexité asymptotique de nombreux algorithmes récursifs.
Arbres de récursion
Une autre méthode consiste à représenter chaque appel récursif par un noeud d'un arbre.
Chaque niveau correspond à une profondeur récursive.
Le coût total est obtenu en additionnant les coûts de tous les niveaux.
Cette approche est particulièrement utile pour le tri fusion et le tri rapide.
Conditions d'arrêt
Toute relation récursive doit posséder un cas de base.
Sans condition d'arrêt, la récursion devient infinie.
Par exemple :
|
SI n=0 ALORS RETOURNER SINON Appel récursif FIN SI |
Récursion terminale
Une récursion est dite terminale lorsque l'appel récursif constitue la dernière opération effectuée.
Les compilateurs peuvent parfois transformer automatiquement cette récursion en boucle.
Cela réduit la consommation de pile.
Profondeur de récursion
Une récursion de profondeur :
| n |
utilise généralement :
| O(n) |
cadres de pile.
Une profondeur trop importante peut provoquer un débordement de pile.
Conversion en boucle
Certaines relations de récurrence peuvent être calculées de manière itérative.
Par exemple :
|
MODULE Suite(n) a ← 0 POUR i ← 1 JUSQU'A n a ← a+2 FIN POUR RETOURNER a |
Cette version évite les appels récursifs.
Optimisation mémoire
Certaines récurrences n'ont besoin que des derniers termes.
Pour Fibonacci :
|
ancien courant suivant |
suffisent.
La mémoire devient :
| O(1) |
au lieu de :
| O(n) |
Récurrences mutuelles
Deux fonctions peuvent être définies l'une par l'autre.
Exemple :
|
Pair(n) Impair(n) |
Chaque fonction appelle l'autre.
Ce type de relation est appelé récurrence mutuelle.
Détection de cycles
Certaines récurrences produisent une suite périodique.
Par exemple :
|
an+1 = (an2+1) mod m |
Comme le nombre d'états est fini, un cycle apparaît nécessairement.
Le principe des tiroirs garantit cette répétition.
Relation de récurrence probabiliste
Certaines récurrences utilisent des espérances mathématiques.
Exemple :
|
E(n) = 1 + ½E(n-1) + ½E(n-2) |
Elles apparaissent dans l'analyse moyenne des algorithmes.
Complexité spatiale
L'entreposage des valeurs dépend de la méthode utilisée.
| Méthode | Mémoire |
|---|---|
| Récursion naïve | O(n) |
| Itération | O(1) |
| Mémoïsation | O(n) |
| Matrice | O(1) hors calcul matriciel |
Algorithme itératif général
|
MODULE CalculSuite(n) Initialiser les conditions initiales POUR i ← début JUSQU'A n Calculer le terme suivant FIN POUR RETOURNER terme recherché |
Algorithme récursif
|
MODULE Suite(n) SI cas de base ALORS RETOURNER valeur FIN SI RETOURNER relation récursive |
Exemple Java
- public class FibonacciDP {
-
- public static long fibonacci(int n) {
-
- if (n < 2)
- return n;
-
- 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) {
-
- System.out.println(
- fibonacci(40)
- );
-
- }
-
- }
Tableau comparatif
| Relation | Complexité |
|---|---|
| T(n)=T(n-1)+1 | O(n) |
| T(n)=T(n/2)+1 | O(log n) |
| T(n)=2T(n/2)+n | O(n log n) |
| T(n)=3T(n/2)+n | O(n^log23) |
| T(n)=aT(n/b)+f(n) | Théorème maître |
Applications
Les relations de récurrence sont utilisées dans :
- les suites numériques ;
- les nombres de Fibonacci ;
- les nombres de Catalan ;
- les nombres de Stirling ;
- les fonctions génératrices ;
- les automates ;
- les graphes ;
- les arbres binaires ;
- la programmation dynamique ;
- les algorithmes récursifs ;
- la cryptographie ;
- le traitement du signal ;
- les simulations ;
- les probabilités ;
- les méthodes numériques ;
- l'analyse de complexité.
Avantages
Les relations de récurrence présentent plusieurs avantages :
- elles décrivent naturellement une évolution progressive ;
- elles modélisent efficacement les algorithmes récursifs ;
- elles permettent d'étudier la complexité ;
- elles facilitent la programmation dynamique ;
- elles offrent plusieurs méthodes de résolution ;
- elles permettent des calculs incrémentaux ;
- elles réduisent parfois la mémoire nécessaire ;
- elles possèdent de nombreuses applications pratiques.
Limites et précautions
Plusieurs précautions doivent être prises :
- les conditions initiales sont indispensables ;
- une récursion mal conçue peut provoquer une explosion exponentielle ;
- certaines récurrences ne possèdent pas de solution fermée simple ;
- les débordements de pile sont possibles ;
- les erreurs de conditions d'arrêt conduisent à une récursion infinie ;
- certaines méthodes de résolution ne s'appliquent qu'aux coefficients constants ;
- les calculs peuvent rapidement dépasser la capacité des types numériques ;
- une solution explicite n'est pas toujours plus efficace qu'un calcul itératif.
Remarque
Les relations de récurrence constituent un lien naturel entre les mathématiques discrètes et la programmation. Elles permettent de décrire l'évolution d'une suite, d'analyser les algorithmes récursifs et de modéliser de nombreux phénomènes informatiques. Leur étude conduit directement à la programmation dynamique, aux fonctions génératrices, au théorème maître, aux nombres de Fibonacci, aux nombres de Catalan et à l'analyse asymptotique des algorithmes. Elles représentent ainsi l'un des outils les plus importants des mathématiques appliquées à l'informatique moderne.