Récursion en Python
Une fonction récursive résout une instance à partir des résultats d'instances plus petites du même problème.
def tree_size(node) -> int:
if node is None:
return 0
return 1 + tree_size(node.left) + tree_size(node.right)
Liste de contrôle de correction
- Cas de base : renvoyer directement le résultat de la plus petite instance.
- Mesure de progression : chaque appel récursif se rapproche strictement d'un cas de base.
- Contrat inductif : supposer les résultats récursifs corrects, puis les combiner correctement pour l'instance courante.
- Responsabilité de l'état : copier, restaurer ou délimiter volontairement les accumulateurs mutables.
Modèle de coût
Comptez à la fois le nombre d'appels et le travail de chacun. Le pic d'espace de pile dépend de la profondeur active maximale, pas du nombre total de nœuds dans l'arbre de récursion.
Python ne garantit pas l'élimination des appels terminaux et l'interpréteur limite la profondeur de récursion pour protéger la pile du processus. Une récursion linéaire profonde doit généralement devenir une itération avec une pile explicite.
Quand la récursion convient
- arbres et syntaxes imbriquées ;
- algorithmes de division pour régner ;
- recherche en profondeur et retour sur trace ;
- définitions mathématiques naturellement récursives lorsque la profondeur d'entrée est maîtrisée.
Sous-problèmes répétés
La récursion seule n'est pas synonyme d'inefficacité, mais les appels qui se chevauchent peuvent causer une répétition exponentielle. functools.cache ou lru_cache peuvent mémoïser des appels purs aux arguments hachables ; les caches conservent les références des arguments et résultats et exigent une politique de durée de vie explicite dans les processus longs.
Ne mettez pas en cache une fonction à effets de bord, dépendante du temps, aléatoire, génératrice ou renvoyant un résultat mutable simplement parce qu'elle est récursive.
Un arbre complet et ses hypothèses
Ici, None représente un sous-arbre vide. Chaque autre nœud doit avoir des attributs
left et right. La structure doit être un arbre fini : aucun cycle, ni nœud
partagé entre branches si l'objectif est de compter les nœuds distincts.
from dataclasses import dataclass
@dataclass
class Node:
left: "Node | None" = None
right: "Node | None" = None
tree = Node(Node(), Node(Node()))
assert tree_size(None) == 0
assert tree_size(Node()) == 1
assert tree_size(tree) == 4
Chaque feuille renvoie 1 + 0 + 0 ; son parent additionne les tailles des deux
sous-arbres disjoints et ajoute un pour lui-même. Le nombre de nœuds du sous-arbre
courant est un entier non négatif qui diminue strictement à chaque descente non
vide. Cela justifie la terminaison, contrairement à la seule présence d'un cas
de base. Pour n nœuds et une hauteur h, le travail est linéaire en n et le
pic de pile récursive est linéaire en h, en supposant les accès aux attributs
et les additions d'entiers de coût constant.
Le même contrat peut éviter les appels récursifs :
def tree_size_iterative(node):
pending = [] if node is None else [node]
count = 0
while pending:
current = pending.pop()
count += 1
if current.right is not None:
pending.append(current.right)
if current.left is not None:
pending.append(current.left)
return count
assert tree_size_iterative(tree) == tree_size(tree)
assert tree_size_iterative(None) == 0
Aucune version ne détecte les cycles. Un parcours de graphe exige un ensemble de
nœuds visités et une définition explicite du comptage des nœuds partagés.
Dans CPython, une profondeur excessive lève RecursionError ; la profondeur sûre
exacte n'est pas portable. La documentation de sys
prévient qu'une limite trop élevée peut faire planter l'interpréteur. La
mémoïsation réduit le travail répété, pas la plus longue chaîne d'appels.