À retenir
- Une fonction récursive est une fonction qui s'appelle elle-même.
- Elle nécessite toujours une condition de sortie pour s'arrêter.
- Elle est souvent plus élégante et lisible qu'une boucle pour traiter des structures complexes.
La récursion est une technique de programmation où une fonction résout un problème en s'appelant elle-même avec des données plus simples. On peut l'imaginer comme une série de poupées russes (matriochkas) : pour atteindre le cœur du problème, on doit ouvrir chaque poupée l'une après l'autre jusqu'à la plus petite.
Étymologie
Vient du latin recurrere (« revenir en arrière », « courir à nouveau »). Le terme a d'abord été utilisé en mathématiques et en logique pour définir des suites de nombres avant d'être adopté par l'informatique pour désigner l'auto-référence des fonctions.
Exemples d'usage
- Exploration de fichiers : Pour lister tous les documents d'un dossier, l'ordinateur liste le dossier actuel, puis s'appelle lui-même pour chaque sous-dossier trouvé.
- Calcul de la factorielle : Pour calculer 5!, on multiplie 5 par le résultat de 4!, lequel est calculé en appelant à nouveau la fonction.
- Algorithmes de tri : Le
Quicksortdivise une liste en deux et s'applique récursivement sur chaque moitié.
Cas d'usage
La récursion intervient principalement dans la manipulation de structures de données hiérarchiques (arbres, graphes), comme le DOM d'une page web (HTML) ou l'arborescence d'un système de fichiers. Elle est aussi très présente en programmation fonctionnelle et en intelligence artificielle.
Bonnes pratiques
Il faut impérativement définir un cas de base (une condition d'arrêt) pour éviter que la fonction ne tourne à l'infini. Il faut aussi être vigilant sur la consommation de mémoire, car chaque appel s'ajoute à la pile d'exécution (stack).
Synonymes
Antonymes
Conseil
Pour bien comprendre la récursion quand on débute, essayez de tracer l'exécution sur papier : dessinez chaque appel de fonction comme une nouvelle boîte qui attend le résultat de la boîte suivante pour se terminer.
Questions fréquentes
Quelle est la différence avec l'itération ?
L'itération utilise des boucles (for, while) pour répéter une action, tandis que la récursion utilise des appels de fonctions imbriqués.
Pourquoi dit-on que la récursion est risquée ?
Si la récursion est trop profonde ou sans condition d'arrêt, elle provoque un 'Stack Overflow' (dépassement de pile), ce qui fait planter le programme par manque de mémoire.