Récursion — fonctionnement, exemples et cas de base

En mathématiques, la récursion consiste à définir une fonction, une suite ou un processus à l’aide de cas plus petits de la même idée. Une définition récursive ne fonctionne que si elle comprend un cas de base et une règle qui rapproche chaque nouveau cas de ce cas de base.

Si vous ne retenez que l’idée essentielle, c’est celle-ci : la récursion cesse d’être utile dès que la règle de réduction n’atteint plus un point d’arrêt valide.

Ce que signifie la récursion en mathématiques

Une définition récursive n’énumère pas chaque cas séparément. À la place, elle donne un point de départ et une règle pour construire les cas plus grands à partir des plus petits.

C’est différent d’une formule explicite. Une formule explicite donne la réponse à partir de l’entrée en une seule expression. Une définition récursive réduit le problème étape par étape jusqu’à atteindre un cas déjà connu.

Pourquoi un cas de base est nécessaire

Le cas de base est le point d’arrêt. Sans lui, la définition continue de renvoyer à des cas de plus en plus petits sans jamais se terminer.

Le cas de base doit aussi être compatible avec la règle choisie. Si l’étape récursive fait passer de $n$ à $n-1$, alors le cas de base doit pouvoir être atteint selon ce schéma pour les entrées autorisées.

Exemple détaillé : la factorielle définie par récursion

La factorielle est une définition récursive classique. Pour les entiers $n \ge 0$, on définit la factorielle par

$$0! = 1$$

et, pour $n \ge 1$,

$$n! = n(n-1)!$$

Ici, $0! = 1$ est le cas de base, et $n! = n(n-1)!$ est l’étape récursive.

Pour calculer $4!$, on réduit jusqu’à ce que le cas de base apparaisse :

$$4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!$$

On applique maintenant le cas de base $0! = 1$ :

$$4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$$

C’est le schéma complet de la récursion : réduire à un cas plus petit, atteindre le cas de base, puis remonter jusqu’à la question de départ.

Récursion ou relation de récurrence

La récursion est l’idée la plus générale. Une relation de récurrence est une règle récursive pour une suite, où chaque terme dépend des termes précédents.

Par exemple, la suite de Fibonacci est donnée par une relation de récurrence, car chaque terme est défini à partir des termes antérieurs. La factorielle est elle aussi récursive, mais elle est généralement présentée comme une définition récursive d’une fonction plutôt que comme une relation de récurrence pour une suite.

Erreurs fréquentes en récursion

Oublier le cas de base

S’il n’y a pas de cas de base, la définition ne se termine pas.

Utiliser une étape qui ne réduit pas le problème

Si l’étape récursive ne rapproche pas du cas de base, le processus peut tourner indéfiniment ou devenir non défini pour certaines entrées.

Oublier la condition sur la règle

Dans l’exemple de la factorielle, la règle $n! = n(n-1)!$ s’utilise pour $n \ge 1$. Cette condition est importante. Sans elle, on pourrait essayer d’appliquer la règle là où la définition n’était pas prévue.

Penser que la récursion n’est qu’une idée de programmation

La récursion existe en mathématiques bien avant le code. C’est une manière de définir des fonctions, des suites et des ensembles en renvoyant à des cas plus petits. On utilise ensuite souvent le raisonnement par récurrence pour démontrer des propriétés de ces définitions récursives.

Quand la récursion est utile

La récursion est utile lorsqu’un problème se décompose naturellement en versions plus petites de lui-même. On la retrouve dans les factorielles, les suites de type Fibonacci, les ensembles définis récursivement et de nombreux algorithmes.

Elle est particulièrement utile lorsque le cas plus petit a la même structure que le cas initial. Si le cas plus petit n’est pas vraiment du même type de problème, la récursion n’est généralement pas le bon outil.

Un test rapide pour une définition récursive correcte

Posez-vous deux questions :

1. Ai-je un cas de base ?
2. Chaque étape récursive s’en rapproche-t-elle ?

Si la réponse à l’une des deux questions est non, la définition doit être corrigée.

Essayez un problème similaire

Définissez une suite par

$$a_1 = 2, \qquad a_n = a_{n-1} + 3 \quad \text{for } n \ge 2$$

Puis calculez $a_2$, $a_3$ et $a_4$. C’est un moyen rapide de s’entraîner à repérer le cas de base et l’étape récursive dans un nouveau contexte.