Récursion

La récursion est une méthode où quelque chose est défini en se référant à lui-même. En mathématiques, cela signifie qu’un nouveau terme d’une suite, d’une fonction ou d’un ensemble dépend des étapes précédentes. De cette façon, des structures complexes peuvent être construites à partir d’un début simple.

 

Un exemple simple est une suite définie récursivement :

 

$$ \large a_{n} = 2 \cdot a_{n-1}, \quad a_{0} = 1 $$

 

Le point de départ est \( \large a_{0} = 1 \). Chaque nouveau terme est obtenu en multipliant le précédent par 2. Ainsi, les premières valeurs sont

 

$$ \large a_{1} = 2, \quad a_{2} = 4, \quad a_{3} = 8, \quad a_{4} = 16, \ldots $$

 

Forme récursive et explicite

Une formule récursive décrit un terme à partir des précédents. Souvent, on peut aussi trouver une formule explicite, où chaque terme se calcule directement sans connaître les précédents. Pour l’exemple ci-dessus, on a

 

$$ \large a_{n} = 2^n $$

 

Les définitions récursives sont utiles pour montrer une structure, tandis que les formules explicites sont rapides pour le calcul. Les deux approches sont complémentaires et étroitement liées.

 

Suites

La récursion est utilisée pour définir de nombreuses suites connues. Par exemple, la suite de Fibonacci, où chaque terme est la somme des deux précédents.

 

$$ \large F_{n} = F_{n-1} + F_{n-2}, \quad F_{0} = 0, \quad F_{1} = 1 $$

 

Fonctions

Un autre exemple est la fonction factorielle. Elle peut être définie récursivement comme suit :

 

$$ \large n! = n \cdot (n-1)!, \quad 0! = 1 $$

 

Ensembles

Les ensembles peuvent également être définis récursivement. Si l’on commence par dire que 3 appartient à l’ensemble, puis qu’on ajoute la somme des éléments déjà connus, on obtient tous les nombres divisibles par 3. Cela peut s’écrire comme une définition récursive :

 

$$ \large 3 \in M, \quad x \in M \;\Rightarrow\; x + 3 \in M $$

 

Triangle de Pascal

Un exemple géométrique bien connu est le triangle de Pascal. Chaque nombre est formé récursivement comme la somme des deux nombres au-dessus. Cela donne une structure triangulaire qui contient les coefficients binomiaux.

 

$$ \large
\begin{array}{cccccccccccccccccc}
        &       &       &       &       &       &       &       & 1     &       &       &       &       &       &       &       \\
        &       &       &       &       &       &       & 1     &       & 1     &       &       &       &       &       &       \\
        &       &       &       &       &       & 1     &       & 2     &       & 1     &       &       &       &       &       \\
        &       &       &       &       & 1     &       & 3     &       & 3     &       & 1     &       &       &       &       \\
        &       &       &       & 1     &       & 4     &       & 6     &       & 4     &       & 1     &       &       &       \\
        &       &       & 1     &       & 5     &       & 10    &       & 10    &       & 5     &       & 1     &       &       \\
        &       & 1     &       & 6     &       & 15    &       & 20    &       & 15    &       & 6     &       & 1     &       \\
        & 1     &       & 7     &       & 21    &       & 35    &       & 35    &       & 21    &       & 7     &       & 1     \\
  1     &       & 8     &       & 28    &       & 56    &       & 70    &       & 56    &       & 28    &       & 8     &       & 1 \\
\end{array}
$$

 

 

Application

La récursion est un outil fondamental en mathématiques discrètes. Elle sert à décrire des processus infinis, à démontrer des propriétés à l’aide de l’induction et à construire des algorithmes. En géométrie, la récursion joue aussi un rôle, par exemple dans la construction des fractales.

 

Lien avec l’induction

Lorsqu’on travaille avec des définitions récursives, l’induction est un outil de démonstration naturel. On montre d’abord qu’une affirmation est vraie dans le cas de base, puis qu’elle reste valable d’une étape à l’autre. Ainsi, on peut démontrer des propriétés pour toute la structure infinie définie récursivement.