À retenir
- Une fonction récursive s'appelle elle-même.
- Elle divise un problème complexe en sous-problèmes identiques plus simples.
- Elle doit obligatoirement posséder une condition de sortie pour éviter une boucle infinie.
La récursivité est un procédé où une fonction ou un programme fait appel à lui-même pour résoudre un problème. On peut comparer cela à des miroirs qui se font face ou à des poupées russes : pour accomplir une tâche globale, on répète la même action sur des morceaux de plus en plus petits jusqu'à atteindre un élément final simple.
Étymologie
Issu du latin recurrere signifiant « revenir en arrière » ou « courir de nouveau ». En informatique, ce terme s'est imposé pour décrire des structures ou des fonctions qui s'auto-référencent.
Exemples d'usage
- Le calcul de la factorielle en mathématiques (n! = n × (n-1)!).
- L'exploration des dossiers d'un disque dur : pour lister tous les fichiers, on liste ceux du dossier actuel, puis on recommence la même opération pour chaque sous-dossier trouvé.
Cas d'usage
Elle est omniprésente dans le traitement de données hiérarchiques (arbres, dossiers), les algorithmes de tri complexe (comme le tri rapide) et dans certains langages de programmation fonctionnels où les boucles traditionnelles sont peu utilisées.
Bonnes pratiques
Le point le plus critique est de définir une condition d'arrêt (ou cas de base). Sans elle, la fonction s'appellerait à l'infini, provoquant un plantage du programme par saturation de la mémoire vive (le fameux stack overflow).
Synonymes
Antonymes
Conseil
Pour bien comprendre la récursivité quand on débute, essayez de la dessiner sur papier sous forme d'escalier : chaque marche est un nouvel appel, et on ne peut remonter l'escalier (finir le calcul) que lorsqu'on a touché le sol (la condition d'arrêt).
Questions fréquentes
Pourquoi utiliser la récursivité plutôt qu'une boucle ?
Elle permet souvent d'écrire un code plus court, plus élégant et plus facile à comprendre pour des structures de données complexes comme les arbres de fichiers.
Est-ce plus performant ?
Pas forcément. La récursivité consomme plus de mémoire (pile d'appels) qu'une boucle classique. Pour de très grands volumes de données, une boucle (itération) est souvent préférable pour éviter de saturer la mémoire.