Définitions récursives

Une définition récursive est une façon de décrire un objet mathématique en se référant à lui-même. Pour qu’une telle définition ait un sens, elle doit toujours comporter deux parties :

 

• Base : la ou les premières étapes qui initient le processus.
• Étape récursive : une règle qui explique comment former de nouveaux éléments à partir des précédents.

 

 

Fonctions

Un exemple classique est la fonction factorielle. Voici la base et l’étape récursive :

 

$$ \large 0! = 1 $$

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

 

La base indique la valeur de \( \large 0! \). Ensuite, l’étape récursive décrit comment \( \large n! \) est calculé à partir de \( \large (n-1)! \). Ainsi, toutes les valeurs de la factorielle peuvent être obtenues pas à pas.

 

Exemple

On peut calculer les premières valeurs :

 

$$ \large 0! = 1 \quad \text{(base)} $$

$$ \large 1! = 1 \cdot 0! = 1 $$

$$ \large 2! = 2 \cdot 1! = 2 $$

$$ \large 3! = 3 \cdot 2! = 6 $$

$$ \large 4! = 4 \cdot 3! = 24 $$

 

Chaque étape se construit directement sur la précédente, jusqu’à atteindre la valeur souhaitée.

 

 

Fonctions sur les chaînes

Les définitions récursives peuvent aussi s’appliquer aux chaînes de symboles. Un exemple est la fonction \( \large L(s) \), qui donne la longueur d’une chaîne \( \large s \) :

 

$$ \large L(\varepsilon) = 0 $$

$$ \large L(x \cdot s) = 1 + L(s) $$

 

Ici, \( \large \varepsilon \) désigne la chaîne vide, et \( \large x \cdot s \) est une chaîne composée d’un premier symbole \( \large x \) suivi du reste \( \large s \). La base dit que la chaîne vide a une longueur de 0, et l’étape récursive dit que la longueur d’une chaîne plus longue s’obtient en ajoutant 1 à la longueur du reste.

 

 

Résumé

Une définition récursive est toujours construite à partir d’un point de départ clair et d’une règle pour avancer. Cette division en base et étape récursive permet de construire des structures complexes de manière précise et systématique. Qu’il s’agisse de nombres, de chaînes ou de figures géométriques, les définitions récursives sont un outil fondamental.