Bases & algorithmique · 6 mondes · 18 étapes
Algorithmique
Apprendre à penser un problème, en Python, dans le navigateur.
Progression
0 %
0/18 étapes terminées
Avancé · 10 min de lecture
La récursivité
Cas de base, pile d'appels, mémoïsation
1Définition
Une fonction récursive s'appelle elle-même sur un problème strictement plus petit. Elle comporte toujours un cas de base qui répond sans rappeler, et un cas récursif qui réduit le problème.
2Principes fondamentaux
01
Le cas de base d'abord
C'est lui qui garantit l'arrêt. On l'écrit avant même de réfléchir au reste.
02
Réduire vraiment
Chaque appel doit rapprocher du cas de base : n - 1, liste[1:], la moitié. Sinon, RecursionError.
03
Faire confiance à l'appel
On suppose que la fonction sait résoudre le cas plus petit, et on en déduit le cas courant. Chercher à dérouler tous les niveaux dans sa tête est le meilleur moyen de se perdre.
04
Mémoïser les recouvrements
Si les mêmes sous-problèmes reviennent (Fibonacci), un dictionnaire de cache fait passer d'exponentiel à linéaire.
3Exemples pratiques
Fibonacci, avant et après le cache
1def fib(n): # O(2ⁿ) : 2 692 537 appels pour n = 302 if n <= 1:3 return n4 return fib(n - 1) + fib(n - 2)5 6cache = {}7 8def fib_rapide(n): # O(n) : 59 appels9 if n <= 1:10 return n11 if n in cache:12 return cache[n]13 cache[n] = fib_rapide(n - 1) + fib_rapide(n - 2)14 return cache[n]Deux lignes de cache, et le même algorithme devient utilisable. C'est le meilleur rapport gain/effort de toute l'algorithmique.
Parcourir une structure imbriquée
1def total(element):2 if isinstance(element, list):3 somme = 04 for e in element:5 somme = somme + total(e)6 return somme7 return element8 9print(total([4, [8, [15, 16]], [23], 42])) # 108La boucle parcourt un niveau, la récursivité descend les niveaux. Aucune profondeur maximale à prévoir : c'est ainsi qu'on parcourt un arbre de fichiers.
4Erreurs courantes
Pas de cas de base
À éviter
def compte(n): return 1 + compte(n - 1)À faire
def compte(n): if n <= 0: return 0 return 1 + compte(n - 1)Pourquoi : RecursionError après environ mille appels empilés.
Un cas récursif qui ne réduit rien
À éviter
return somme(liste)À faire
return liste[0] + somme(liste[1:])Pourquoi : Le même problème est repassé à l'identique : la descente ne s'arrête jamais.
Oublier de renvoyer le résultat
À éviter
def somme(liste): if not liste: return 0 liste[0] + somme(liste[1:])À faire
return liste[0] + somme(liste[1:])Pourquoi : Sans return, la fonction renvoie None et l'addition du niveau supérieur échoue.
5Subtilités à connaître
- ◆Python limite la pile à environ 1 000 appels : les récursions très profondes s'écrivent en boucle.
- ◆
functools.lru_cachemémoïse une fonction en une ligne de décorateur, sans écrire le dictionnaire. - ◆Une récursion terminale (le résultat de l'appel est renvoyé tel quel) s'écrit trivialement en boucle ; Python n'optimise pas ce cas lui-même.
6Vérifie ta compréhension
Question 1/3
Score 0
Que manque-t-il à une récursion qui provoque une RecursionError ?
Envie d'essayer ? Ouvre le Labo et recopie les exemples pour les modifier.