En bref
La récursivité, c’est une fonction qui s’appelle elle-même pour résoudre un problème en le réduisant à une version plus petite de lui-même — jusqu’à atteindre un cas si simple qu’on connaît la réponse directement. Pense aux poupées russes : pour compter les poupées, tu en ouvres une et tu comptes « 1 plus le nombre de poupées dans celle-ci » — et tu répètes, jusqu’à la toute petite qui ne s’ouvre pas : le cas de base, la condition d’arrêt sans laquelle tout s’effondre. Chaque appel en attente s’empile dans la mémoire (la pile d’appels), puis les réponses remontent en cascade. La récursivité n’est pas un gadget de virtuose : c’est l’outil naturel des problèmes emboîtés — parcourir des dossiers qui contiennent des dossiers, explorer un arbre généalogique — et un formidable révélateur de compréhension. La règle d’or tient en deux questions : quel est mon cas de base ? et chaque appel rapproche-t-il de lui ?
Voici le concept qui donne le vertige à tous les débutants — et le sourire à tous ceux qui l’ont apprivoisé. Une fonction peut s’appeler elle-même : c’est légal, c’est puissant, et c’est déroutant la première fois. Comprendre la récursivité — son mécanisme, sa condition d’arrêt, ses vrais usages — se fait très bien en douceur : ce guide s’y emploie, poupées russes en main, dans la lignée de notre guide complet pour apprendre à coder.
La récursivité, expliquée avec les mains
Prends des poupées russes et pose-toi la question : combien y en a-t-il ? Ta méthode naturelle est récursive sans le savoir : « j’ouvre la poupée ; la réponse, c’est 1 plus le nombre de poupées à l’intérieur » — et pour compter l’intérieur, tu appliques… la même méthode. La chaîne descend, de poupée en poupée, jusqu’au moment décisif : la toute petite, celle qui ne s’ouvre pas — là, pas besoin de méthode, la réponse est directe : 1. C’est le cas de base, et il est la clé de voûte du concept : sans lui, la méthode s’appellerait à l’infini. Puis les réponses remontent : la petite dit 1, sa maman dit 1 + 1 = 2, la suivante 1 + 2 = 3… jusqu’à la première, qui annonce le total.
Tu viens de voir les trois pièces de toute récursion : un cas de base (le problème si petit qu’on répond directement), un cas récursif (« la réponse = un petit travail + la même question en plus petit »), et la garantie de rapprochement (chaque appel doit se rapprocher du cas de base — chaque poupée est plus petite que la précédente). Et une quatrième pièce, en coulisses : pendant la descente, chaque appel en attente reste ouvert dans la mémoire — les poupées ouvertes alignées sur la table — dans ce qu’on nomme la pile d’appels ; la remontée des réponses les referme une à une. Cette pile explique tout : pourquoi ça marche, et pourquoi une récursion sans cas de base finit par déborder — la table n’est pas infinie.
À quoi ça ressemble dans le code
En Python, le classique des classiques — le compte à rebours : def compte_a_rebours(n): — si n vaut zéro, afficher « Partez ! » et s’arrêter (le cas de base) ; sinon, afficher n puis appeler compte_a_rebours(n – 1) (le cas récursif, avec son n – 1 qui garantit le rapprochement). Appelle compte_a_rebours(3) et déroule mentalement : 3 s’affiche, appel avec 2 ; 2 s’affiche, appel avec 1 ; 1 s’affiche, appel avec 0 ; « Partez ! » — et les appels se referment en remontant. Le deuxième classique, la factorielle (5! = 5 × 4 × 3 × 2 × 1), montre la remontée qui calcule : def factorielle(n): return 1 if n <= 1 else n * factorielle(n – 1) — la réponse de chaque étage attend celle de l’étage du dessous, puis les multiplications remontent en cascade : 1, puis 2, puis 6, 24, 120.
En JavaScript, l’orthographe change, pas la musique : function factorielle(n) { if (n <= 1) return 1; return n * factorielle(n – 1); } — cas de base d’abord, appel réduit ensuite, littéralement la même structure. Une remarque honnête pour finir le tour : tout ce que fait une récursion, une boucle peut souvent le faire aussi — le compte à rebours en boucle est même plus simple. La récursivité prend l’avantage sur les problèmes naturellement emboîtés : parcourir un dossier qui contient des dossiers qui contiennent des dossiers, explorer un arbre (généalogique, de décisions, de fichiers) — là, la version récursive tient en cinq lignes limpides quand la boucle se contorsionne. C’est l’outil des structures en poupées russes — on le ressort exactement quand le problème en est une, et les exercices Python comme JavaScript t’en donnent l’occasion.
Les pièges classiques (et comment les éviter)
Piège 1 : le cas de base absent ou inatteignable. La récursion sans porte de sortie s’appelle elle-même jusqu’au débordement de la pile — le fameux « maximum recursion depth » de Python ou « stack overflow » ailleurs : le rite de passage du concept. Le remède rituel, avant d’écrire le moindre appel : formuler le cas de base à voix haute (« si n vaut zéro, je renvoie… »), et l’écrire en premier dans la fonction. Piège 2 : l’appel qui ne rapproche pas. Appeler factorielle(n) au lieu de factorielle(n – 1) — ou réduire le mauvais paramètre — donne une descente sans fin malgré un cas de base parfait. Le remède : vérifier que chaque appel travaille sur un problème strictement plus petit.
Piège 3 : oublier le return dans la remontée. En Python, n * factorielle(n – 1) sans return calcule… et jette le résultat — la cascade remonte du vide. Le remède : dans une récursion qui calcule, chaque branche renvoie — le réflexe return déjà ancré depuis les fonctions. Piège 4 : la récursivité par réflexe. Résoudre en récursif ce qu’une boucle fait plus simplement complique sans gagner (et coûte de la pile) — le remède est le critère du problème emboîté : structure en poupées russes → récursion ; répétition plate → boucle. Le vertige initial passé, tu tiens un outil de grand : la récursivité est aussi une porte vers les algorithmes élégants — le tri fusion, la recherche dichotomique — et leur analyse de coût, où elle brille de tous ses feux. La petite poupée qui ne s’ouvre pas t’aura mené loin.
Questions fréquentes
C’est quoi la récursivité, en une phrase ?
Une fonction qui s’appelle elle-même pour résoudre un problème en le réduisant à une version plus petite — jusqu’au cas de base, si simple qu’on répond directement, à partir duquel les réponses remontent en cascade. Comme compter des poupées russes : 1 plus le contenu, jusqu’à la petite qui ne s’ouvre pas.
C’est quoi le cas de base d’une récursion ?
La condition d’arrêt : le problème devenu si petit que la réponse est directe, sans nouvel appel (n égal à zéro pour un compte à rebours, la liste vide, la poupée qui ne s’ouvre pas). Sans cas de base atteignable, la fonction s’appelle à l’infini jusqu’au débordement de la pile d’appels.
Récursivité ou boucle : que choisir ?
Le critère est la forme du problème : répétition plate (compter, additionner, parcourir une liste) → boucle, plus simple et plus économe ; structure emboîtée (dossiers dans des dossiers, arbres, problèmes qui se divisent) → récursivité, dont la version tient en quelques lignes limpides là où la boucle se contorsionne.
Que signifie l’erreur « maximum recursion depth » ou « stack overflow » ?
Que la pile d’appels a débordé : la fonction s’est appelée trop de fois sans atteindre son cas de base — soit il manque, soit les appels ne s’en rapprochent pas (mauvais paramètre réduit). Le diagnostic : vérifier le cas de base, puis que chaque appel travaille sur un problème strictement plus petit.
Sources
- Python.org — la documentation officielle du langage
- MDN Web Docs — la référence JavaScript en français
Cet article a une vocation informative et pédagogique. Les plateformes, outils et formations éventuellement cités le sont à titre d’exemple ; compare plusieurs options avant de t’engager ou de payer.