Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / Python

Récursivité

Une fonction récursive résout des sous-problèmes plus petits et termine chaque branche par un cas de base.

Version : Python 3.14; repository image, production runtime not attested

Syntaxe

def depth(node):
    if not node:
        return 0
    return 1 + max(depth(child) for child in node)

Une fonction récursive résout des sous-problèmes plus petits et termine chaque branche par un cas de base.

Pour un arbre de listes, un nœud vide a une profondeur nulle, sinon on ajoute un à la profondeur maximale des enfants. La pile croît avec la profondeur. Un cycle peut ne jamais atteindre le cas de base et lever RecursionError.

Les profondeurs de [] et [[], [[]]] sont 0 et 2.

def depth(node):
    if not node: return 0
    return 1+max(depth(child) for child in node)
assert depth([[],[[]]])==2
loop=[]
loop.append(loop)
try: depth(loop)
except RecursionError: pass
else: raise AssertionError

Exemples

def depth(node):
    if not node:
        return 0
    return 1 + max(depth(child) for child in node)

print(depth([]), depth([[], [[]]]))

Résultat

0 2

Les profondeurs de [] et [[], [[]]] sont 0 et 2.

Sources