La récursion
Quand une fonction s'appelle elle-même : cas de base, pile d'appels, et diviser pour régner
§1.Une idée qui semble impossible
Une fonction RÉCURSIVE est une fonction qui s'appelle elle-même. Écrit comme ça, on dirait un serpent qui se mord la queue, ou une définition circulaire qui ne définit rien.
Elle fonctionne pourtant, à une condition absolue : il doit exister un CAS DE BASE, une situation où la fonction répond directement, sans se rappeler. Et chaque appel doit se rapprocher de ce cas.
Ce n'est pas un artifice de programmeur. C'est la traduction directe d'une façon de raisonner : « pour résoudre ce problème de taille n, je suppose savoir résoudre celui de taille n − 1 ». En mathématiques, on appelle ça une récurrence.
def factorielle(n): if n <= 1: # cas de base return 1 return n * factorielle(n - 1) # appel récursif print(factorielle(5))print(factorielle(0))Deux lignes utiles. La définition mathématique dit : n! = n × (n−1)!, et 0! = 1. Le code est la traduction littérale de cette phrase — c'est ce qui rend la récursion si élégante quand le problème s'y prête.
§3.Les deux ingrédients obligatoires
- Le cas de base
- La condition qui répond sans se rappeler. Sans lui, la fonction s'appelle indéfiniment et le programme s'écroule.
- Exemple. if n <= 1: return 1
- La progression vers le cas de base
- Chaque appel doit porter sur un problème STRICTEMENT plus petit. factorielle(n - 1) se rapproche de 1 ; factorielle(n) ne se rapproche de rien.
§4.La pile d'appels
Quand factorielle(5) appelle factorielle(4), le premier appel ne disparaît pas : il se met en PAUSE, en attendant le résultat. Il reste en mémoire, avec la valeur de son n.
Ces appels en attente s'empilent — d'où le nom de PILE d'appels. Quand le cas de base est enfin atteint, on redescend la pile en remontant les résultats un par un.
Comprendre cette pile explique tout : pourquoi la récursion consomme de la mémoire, pourquoi elle peut déborder, et pourquoi ce qui est écrit APRÈS l'appel récursif s'exécute en ordre inverse.
def factorielle(n, profondeur=0): marge = " " * profondeur print(marge + "appel de factorielle(" + str(n) + ")") if n <= 1: print(marge + "cas de base -> 1") return 1 r = n * factorielle(n - 1, profondeur + 1) print(marge + "retour de factorielle(" + str(n) + ") -> " + str(r)) return r factorielle(4)Regarde l'ordre : on descend d'abord jusqu'au cas de base, puis on remonte en calculant. Tous les « retour » se font dans l'ordre INVERSE des appels. C'est le fonctionnement d'une pile — dernier entré, premier sorti.
Augmente progressivement la profondeur jusqu'à provoquer l'erreur, puis lis le message.
§8.Récursion multiple : Fibonacci
Jusqu'ici, chaque appel n'en déclenchait qu'un autre. Une fonction peut aussi s'appeler PLUSIEURS fois — et le comportement change radicalement.
La suite de Fibonacci se définit naturellement ainsi : chaque terme est la somme des deux précédents. La traduction récursive est immédiate… et catastrophiquement inefficace.
appels = 0 def fib(n): global appels appels = appels + 1 if n < 2: return n return fib(n - 1) + fib(n - 2) print(fib(20), "en", appels, "appels")Vingt-et-un mille appels pour calculer le vingtième terme ! Parce que fib(18) est recalculé encore et encore, depuis des branches différentes. Chaque incrément de n double presque le travail : à n = 40, on parle de milliards d'appels.
Si le problème est de recalculer sans cesse la même chose, la solution est de mémoriser les résultats.
def fib_memo(n, cache={}): if n < 2: return n if n in cache: return cache[n] cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache) return cache[n] print(fib_memo(20))print(fib_memo(60))Un dictionnaire garde les résultats déjà calculés. Le nombre d'appels passe de vingt mille à une vingtaine — et fib(60), inatteignable en récursion naïve, devient instantané. Cette technique s'appelle la MÉMOÏSATION, et c'est la porte d'entrée vers la programmation dynamique.
§11.Là où la récursion est vraiment le bon outil
Pour la factorielle ou Fibonacci, une boucle fait aussi bien, souvent mieux. La récursion s'impose quand le problème se DÉCOMPOSE naturellement en sous-problèmes de même nature.
C'est le cas du tri fusion du chapitre précédent : trier une liste, c'est trier deux demi-listes puis les fusionner. Écrire ça avec des boucles serait laborieux ; en récursion, c'est trois lignes.
C'est aussi le cas des tours de Hanoï, où la solution récursive est si simple qu'elle en paraît suspecte.
Déplacer une tour de n disques d'un piquet à un autre, sans jamais poser un grand disque sur un petit. Le raisonnement : pour déplacer n disques, il faut d'abord déplacer les n − 1 du dessus ailleurs.
def hanoi(n, depart, arrivee, milieu, mouvements): if n == 0: return hanoi(n - 1, depart, milieu, arrivee, mouvements) mouvements.append(depart + "->" + arrivee) hanoi(n - 1, milieu, arrivee, depart, mouvements) m = []hanoi(3, "A", "C", "B", m)print(len(m), "mouvements")print(" ".join(m))Trois lignes pour un casse-tête qui paraît redoutable. Le nombre de mouvements double à chaque disque ajouté : 2ⁿ − 1. Avec les 64 disques de la légende, il faudrait plus de temps que l'âge de l'univers.
§13.Récursion ou boucle ?
| Situation | Choix | Pourquoi |
|---|---|---|
| Répéter n fois | Boucle | Aucune décomposition, pas de pile inutile |
| Parcourir une liste | Boucle | Plus simple et sans limite de profondeur |
| Diviser en sous-problèmes identiques | Récursion | Tri fusion, dichotomie, Hanoï |
| Structure imbriquée | Récursion | Arbres, dossiers, expressions parenthésées |
| Profondeur potentiellement grande | Boucle | La pile est limitée, surtout ici |
Trois fonctions récursives classiques. Lis-les avec la méthode en trois temps.
§16.La fin du parcours
Douze chapitres : afficher, mémoriser, calculer, décider, répéter, manipuler du texte, structurer en listes, découper en fonctions, associer par clés, comparer des algorithmes, gérer les erreurs, et enfin décomposer récursivement.
Ce sont les fondations complètes. Elles se retrouvent, presque à l'identique, dans tous les langages que tu croiseras — et en Python, tu les as apprises dans celui du bac, des concours et de l'université.
La suite ne se lit pas, elle se pratique. Les soixante exercices corrigés automatiquement sont là pour ça : ils testent tes programmes sur des cas limites que tu n'aurais pas pensé à essayer. C'est en butant sur eux qu'on apprend vraiment.
À retenir
- Une fonction récursive s'appelle elle-même ; il lui faut un CAS DE BASE et une progression vers lui.
- Les appels en attente s'empilent : ce qui suit l'appel récursif s'exécute en ordre inverse.
- La pile est limitée — environ 150 appels imbriqués dans cet atelier, contre ~1000 en Python installé.
- Fibonacci récursif naïf recalcule sans cesse la même chose ; la mémoïsation par dictionnaire règle ça.
- La récursion s'impose quand le problème se décompose en sous-problèmes de même nature.
- Toute récursion peut s'écrire en boucle ; choisis selon la lisibilité et la profondeur attendue.
- Pour l'écrire : cas de base, puis SUPPOSE que n − 1 est résolu, puis vérifie la progression.