À retenir
- C'est la partie de la fonction qui crée l'auto-répétition.
- Il doit toujours manipuler une donnée plus petite ou plus simple que l'appel précédent.
- Il est le moteur de la récursion, mais dépend entièrement du cas de base pour s'arrêter.
Le cas récursif désigne l'étape d'un programme ou d'une formule mathématique où une fonction fait appel à elle-même pour traiter une version réduite ou simplifiée d'un problème. C'est le principe des poupées russes : pour atteindre le cœur, on doit ouvrir une poupée, ce qui nous confronte à une poupée identique mais plus petite, et on recommence l'opération.
Étymologie
Vient du latin recurrere, qui signifie « revenir en arrière » ou « courir à nouveau ». En informatique, ce terme s'est imposé pour décrire des structures qui se répètent en s'imbriquant les unes dans les autres.
Exemples d'usage
- Calcul de la factorielle : Pour calculer la factorielle de 5, on multiplie 5 par la factorielle de 4 (appel récursif).
- Exploration de fichiers : Pour lister le contenu d'un disque, si le programme rencontre un dossier, il s'appelle lui-même pour explorer ce sous-dossier.
- Tri fusion : Un algorithme qui sépare une liste en deux et s'appelle lui-même sur chaque moitié pour les trier.
Cas d'usage
Le cas récursif intervient massivement dans le traitement des structures de données arborescentes (comme les dossiers d'un ordinateur ou le code HTML d'une page web), dans les algorithmes de recherche complexes et dans la résolution de problèmes mathématiques divisibles en sous-problèmes identiques.
Bonnes pratiques
La règle d'or est de s'assurer que chaque passage par le cas récursif rapproche irrémédiablement le programme du cas de base (la condition d'arrêt). Sans cette progression, le programme tournera en boucle jusqu'à épuiser la mémoire de l'ordinateur, provoquant un plantage nommé Stack Overflow.
Synonymes
Antonymes
Conseil
Si vous débutez, essayez de tracer l'exécution d'un cas récursif sur papier. Dessinez chaque appel comme une nouvelle boîte qui s'ouvre. Cela aide à comprendre comment les résultats « remontent » une fois que le cas de base est enfin atteint.
Questions fréquentes
Peut-on remplacer un cas récursif par une boucle ?
Oui, théoriquement tout algorithme récursif peut être transformé en boucle itérative (for ou while), mais le code est souvent moins lisible.
Pourquoi dit-on que c'est risqué pour la mémoire ?
Chaque appel récursif occupe un espace dans la 'pile' de l'ordinateur. Si le cas récursif est appelé trop de fois, cet espace finit par déborder.