Aller au contenu principal

Programmation structurée (Python) · L1 · Section 3/11

Fonctions

Progression

Points d’expérience : XPSérie de jours consécutifs : · —Progression du module : — / —compris

#Fonctions

Une fonction isole une logique réutilisable derrière un nom: elle prend des paramètres, retourne un résultat et documente son contrat. Bien conçue, elle se teste isolément, évite la duplication et rend le programme lisible.

Prérequis: variables et types, boucles.

Objectifs d'apprentissage:

  • Déclarer des fonctions avec paramètres, valeurs par défaut et valeur de retour.
  • Maîtriser les paramètres positionnels, nommés, keyword-only et variadiques (*args, **kwargs).
  • Comprendre la liaison des noms au passage d'arguments et le piège des valeurs par défaut mutables.
  • Écrire une récursion avec cas de base et cas progressif, et visualiser la pile d'appels.

#Déclaration et appel

pythonpython

1def aire(w: float, h: float) -> float:2    """Retourne l'aire d'un rectangle (w et h >= 0)."""3    return w * h4 5print(aire(3, 4))   # 12

Le nom, la docstring et les annotations forment le contrat: ce que la fonction attend (deux flottants positifs) et ce qu'elle garantit (le produit). Une fonction doit retourner son résultat plutôt que l'imprimer: seule la valeur de retour est réutilisable et testable.

pythonpython

1def salue(nom: str, politesse: str = 'Bonjour') -> str:2    return f"{politesse}, {nom} !"3 4print(salue('Ada'))                    # Bonjour, Ada !5print(salue('Alan', politesse='Salut')) # Salut, Alan !

Une valeur par défaut rend un paramètre optionnel. À l'appel, les arguments nommés (politesse='Salut') rendent l'intention explicite et résistent aux réordonnancements de signature.

#Formes de paramètres

pythonpython

1def normalise(valeurs: list[float], *, eps: float = 1e-9) -> list[float]:2    """Ramène les valeurs dans [0, 1]."""3    m, M = min(valeurs), max(valeurs)4    etendue = max(eps, M - m)5    return [(v - m) / etendue for v in valeurs]6 7print(normalise([2, 4, 6]))        # [0.0, 0.5, 1.0]8print(normalise([2, 4, 6], eps=1)) # [0.0, 0.5, 1.0]

Après le *, les paramètres deviennent keyword-only: ils doivent être nommés à l'appel, ce qui évite les confusions d'ordre.

pythonpython

1def resume(titre: str, *points: str, **meta) -> None:2    print(f"# {titre}")3    for p in points:4        print("-", p)5    if meta:6        print("(meta)", meta)7 8resume("Plan", "lire", "tester", auteur="ada")9# Sortie:10# # Plan11# - lire12# - tester13# (meta) {'auteur': 'ada'}

*points collecte les arguments positionnels supplémentaires en tuple, **meta les arguments nommés supplémentaires en dictionnaire.

Ordre des paramètres dans une signature

Positionnels ordinaires, puis *args (ou un * seul), puis keyword-only, puis **kwargs. Exemple valide: def f(a, b=1, *args, c, d=2, **kwargs). Le respect de cet ordre est une règle syntaxique de Python.

#Passage d'arguments: liaison de noms

Python lie chaque paramètre à l'objet passé. Les objets immuables ne peuvent donc pas être modifiés par la fonction; les mutables le peuvent, et l'appelant voit la modification.

pythonpython

1def ajoute(xs: list, x) -> None:2    xs.append(x)          # mutation visible par l'appelant3 4def remplace(n: int) -> int:5    return n + 1          # retourne un nouvel objet, ne touche pas à l'original6 7notes = [12]8ajoute(notes, 15)9print(notes)          # [12, 15]10note = 1211note = remplace(note)12print(note)           # 13

Règle pratique: soit la fonction retourne une nouvelle valeur (style immuable), soit elle modifie en place et retourne None (comme list.sort). Mélanger les deux crée des surprises.

#Récursion

Une fonction récursive s'appelle sur un sous-problème plus petit. Deux obligations: un cas de base qui termine, et un cas progressif qui réduit strictement la distance au cas de base.

pythonpython

1def fact(n: int) -> int:2    if n <= 1:            # cas de base3        return 14    return n * fact(n - 1)  # cas progressif: n diminue5 6print(fact(5))   # 120

Chaque appel occupe un cadre sur la pile; fact(5) empile 5 appels avant de dérouler les multiplications. Dépasser la limite (RecursionError, environ 1000 par défaut) signale une récursion sans cas de base ou trop profonde: convertissez en boucle.

#Visualiser la pile d'appels

main
Sommet
Pile initialisée avec 1 éléments
Étape 1 / 1 | Taille: 1

#Structures définies par récurrence

En algorithmique, la récursion ne sert pas seulement à calculer: elle sert à définir les objets sur lesquels on travaille. Une liste, un arbre, une expression arithmétique se décrivent par un cas de base et des règles de construction, exactement comme une fonction récursive a un cas de base et un cas progressif. Cette symétrie est le cœur du cours: la structure dicte la forme de la fonction, et la définition dicte la forme de la preuve.

Une définition récursive (ou inductive) d'un ensemble comporte deux parties:

  • une base, qui énumère les éléments de départ;
  • des règles, qui construisent un nouvel élément à partir d'éléments déjà construits.

Rien d'autre n'appartient à l'ensemble: c'est le principe d'induction structurelle, qui justifie qu'on puisse raisonner par récurrence sur ces objets.

#Les listes

texttext

1Base     : [] appartient à Listes2Récursion: si L1 appartient à Listes et n est un entier, alors [n] · L1 appartient à Listes

Le symbole · (ou :) est le constructeur « cons »: il accole un élément en tête d'une liste. En Python, cette structure est exactement celle d'une liste, avec L[0] pour la tête et L[1:] pour la queue:

pythonpython

1def taille(L: list) -> int:2    """Nombre d'éléments de L."""3    if L == []:                     # base : la liste vide4        return 05    return 1 + taille(L[1:])        # récursion : tête + queue6 7def div2(L: list) -> list:8    """Liste où chaque valeur est divisée par 2."""9    if L == []:10        return []11    return [L[0] // 2] + div2(L[1:])12 13def mul3(L: list) -> list:14    """Liste où chaque valeur est multipliée par 3."""

Les trois fonctions ont la même charpente: tester la liste vide, traiter la tête, déléguer la queue. Changer la ligne du milieu suffit à changer l'opération. Ce patron s'appelle schéma de récursion structurelle.

#Les arbres binaires

texttext

1Base     : l'arbre vide appartient à AB2Récursion: si g et d appartiennent à AB, alors le nœud (·, g, d) appartient à AB

Un arbre binaire est donc soit vide, soit un nœud portant une valeur et deux sous-arbres. En Python, on représente l'arbre vide par None et un nœud par un triplet:

pythonpython

1# Un arbre est soit None (arbre vide), soit (valeur, sous-arbre gauche, sous-arbre droit)2arbre = (8, (3, (1, None, None), (6, None, None)), (10, None, (14, None, None)))3 4def nb_noeuds(T) -> int:5    if T is None:6        return 07    valeur, g, d = T8    return 1 + nb_noeuds(g) + nb_noeuds(d)9 10def hauteur(T) -> int:11    """Hauteur d'un arbre vide : -1 ; d'une feuille : 0."""12    if T is None:13        return -114    valeur, g, d = T

nb_feuilles illustre un point important: le cas de base n'est pas seulement l'arbre vide, c'est aussi la feuille, où la récursion s'arrête naturellement parce qu'il n'y a plus rien à explorer.

#Transformations d'arbres

Beaucoup d'exercices demandent de reconstruire un arbre modifié plutôt que de le parcourir: la fonction retourne un arbre de même forme, où chaque nœud a été transformé.

pythonpython

1def mul5(T):2    """Arbre où chaque valeur est multipliée par 5."""3    if T is None:4        return None5    valeur, g, d = T6    return (valeur * 5, mul5(g), mul5(d))7 8def pair_impair(T):9    """Nombres pairs remplacés par 'a', impairs par 'b'."""10    if T is None:11        return None12    valeur, g, d = T13    lettre = 'a' if valeur % 2 == 0 else 'b'14    return (lettre, pair_impair(g), pair_impair(d))

La forme de la fonction suit exactement la forme de la définition: un cas pour l'arbre vide, un cas pour le nœud, et deux appels récursifs — un par sous-arbre.

#Expressions et structures à plusieurs constructeurs

Certaines structures ont plusieurs règles de construction. L'ensemble des expressions du cours en est l'exemple:

texttext

1Base     : a appartient à Expr2Récursion: si E1 et E2 appartiennent à Expr, alors E1 * E2 appartient à Expr

La fonction de parcours doit alors distinguer les deux formes possibles de l'argument:

pythonpython

1def nb_a(E) -> int:2    if E == 'a':3        return 14    gauche, droite = E5    return nb_a(gauche) + nb_a(droite)6 7def nb_etoiles(E) -> int:8    if E == 'a':9        return 010    gauche, droite = E11    return 1 + nb_etoiles(gauche) + nb_etoiles(droite)12 13# (a * a) * a, représenté par un couple imbriqué14E = (('a', 'a'), 'a')

Le test E == 'a' est le cas de base; l'autre branche correspond à la règle de construction. Toute fonction sur Expr a exactement cette forme.

#Preuve par récurrence structurelle

Une fois la structure définie inductivement, on démontre ses propriétés par récurrence structurelle: la base de la preuve correspond à la base de la définition, et le pas inductif à chaque règle de construction, en supposant la propriété vraie sur les sous-objets (c'est l'hypothèse de récurrence).

#Premier exemple: la division ne change pas la taille

Énoncé. Pour toute liste L, taille(div2(L)) = taille(L).

Preuve par récurrence sur la structure de L.

Base : L = []. Alors div2([]) vaut [], et taille([]) = 0 = taille([]). La propriété est vraie.

Récurrence : L = [n] · L1, avec L1 une liste plus petite. L'hypothèse de récurrence est taille(div2(L1)) = taille(L1). On calcule:

texttext

1taille(div2(L))  = taille([n // 2] + div2(L1))     par définition de div22                 = 1 + taille(div2(L1))            par définition de taille3                 = 1 + taille(L1)                  par hypothèse de récurrence4                 = taille([n] + L1)                par définition de taille5                 = taille(L)

La propriété est donc vraie pour toute liste. ∎

#Deuxième exemple: chapitres et pages vides

Énoncé. Un livre est construit par: base chapitre; règle, si L1 et L2 sont des livres alors L1 pagevide L2 est un livre. On démontre que le nombre de pagevide égale le nombre de chapitre moins un.

Preuve par récurrence structurelle sur le livre L.

Base : L = chapitre. Il y a 0 page vide et 1 chapitre, et 0 = 1 - 1. Vrai.

Récurrence : L = L1 pagevide L2. Notons p(L) le nombre de pages vides et c(L) le nombre de chapitres. Par construction, p(L) = p(L1) + p(L2) + 1 et c(L) = c(L1) + c(L2). Les hypothèses de récurrence donnent p(L1) = c(L1) - 1 et p(L2) = c(L2) - 1, d'où

texttext

1p(L) = (c(L1) - 1) + (c(L2) - 1) + 12     = c(L1) + c(L2) - 13     = c(L) - 1

La propriété est établie. ∎

#Troisième exemple: feuilles et fleurs

Énoncé. L'ensemble Fleurs est défini par: base l (une feuille); règle, si F1, F2, F3 sont des fleurs alors tige(F1, F2, F3) est une fleur. Montrer que le nombre de feuilles égale deux fois le nombre de fleurs plus un.

Preuve. On note g(X) le nombre de symboles l (les feuilles) et f(X) le nombre de symboles tige (les fleurs) dans l'élément X. On démontre g(X) = 2 f(X) + 1 par récurrence structurelle.

Base : X = l. Alors g(X) = 1 et f(X) = 0, et 2 × 0 + 1 = 1. Vrai.

Récurrence : X = tige(F1, F2, F3). Par construction, g(X) = g(F1) + g(F2) + g(F3) et f(X) = f(F1) + f(F2) + f(F3) + 1 — la tige elle-même compte pour une fleur. Les hypothèses de récurrence donnent g(Fi) = 2 f(Fi) + 1 pour chaque i, d'où

texttext

1g(X) = (2 f(F1) + 1) + (2 f(F2) + 1) + (2 f(F3) + 1)2     = 2 (f(F1) + f(F2) + f(F3)) + 33     = 2 (f(F1) + f(F2) + f(F3) + 1) + 14     = 2 f(X) + 1

La propriété est établie pour toute fleur. ∎

C'est le même schéma que la relation entre nœuds et arêtes d'un arbre: chaque constructeur ajoute un objet d'une sorte et un nombre fixe d'objets d'une autre sorte, et l'invariant de comptage se démontre en une ligne.

#Quatrième exemple: le nombre de a dans une expression

Énoncé. Pour Expr défini par base a et règle E1 * E2, montrer nb_a(E) = nb_etoiles(E) + 1.

Preuve. Base : E = a donne nb_a = 1 et nb_etoiles = 0, soit 1 = 0 + 1. Récurrence : E = E1 * E2; par hypothèse de récurrence nb_a(E1) = nb_etoiles(E1) + 1 et de même pour E2, donc

texttext

1nb_a(E)       = nb_a(E1) + nb_a(E2)2              = (nb_etoiles(E1) + 1) + (nb_etoiles(E2) + 1)3              = (nb_etoiles(E1) + nb_etoiles(E2) + 1) + 14              = nb_etoiles(E) + 1

#Tracer une fonction récursive

Les examens demandent souvent de dérouler une fonction donnée sous forme de pseudocode sur une entrée précise. La méthode est mécanique: à chaque appel, écrire l'argument, déterminer quelle branche s'applique, puis remplacer l'appel par le résultat de ses sous-appels — du plus profond vers la surface.

Soit la fonction suivante, sur une liste d'entiers:

texttext

1function Mistery(X)2  if X = [] then return []3  if X = el · X1 and el > 10 then return Mistery(X1)4  else return el · Mistery(X1)

Appliquée à X = [-5, 16, 14, 3]:

texttext

1Mistery([-5, 16, 14, 3])2  el = -5,  -5 > 10 ? non  ->  -5 · Mistery([16, 14, 3])3Mistery([16, 14, 3])4  el = 16,  16 > 10 ? oui  ->  Mistery([14, 3])5Mistery([14, 3])6  el = 14,  14 > 10 ? oui  ->  Mistery([3])7Mistery([3])8  el = 3,   3 > 10 ? non   ->  3 · Mistery([])9Mistery([])                ->  []

En remontant: 3 · [] = [3], puis [3], puis [3], puis -5 · [3] = [-5, 3]. Le résultat est [-5, 3]. La fonction conserve les éléments inférieurs ou égaux à 10 et supprime les autres: c'est un filtre.

Deux questions accompagnent presque toujours ce genre d'exercice:

La signature. La fonction prend une liste d'entiers en entrée et retourne une liste d'entiers: Mistery : liste[entier] → liste[entier]. Toute fonction récursive sur une structure a une signature qui mentionne cette structure en entrée et en sortie.

La propriété de taille. On démontre que taille(Mistery(X)) ≤ taille(X) par récurrence structurelle. Base: taille([]) = 0 ≤ 0. Récurrence: si el > 10, Mistery(X) = Mistery(X1), donc par hypothèse taille(Mistery(X)) = taille(Mistery(X1)) ≤ taille(X1) < taille(X). Sinon Mistery(X) = el · Mistery(X1), donc taille(Mistery(X)) = 1 + taille(Mistery(X1)) ≤ 1 + taille(X1) = taille(X). Dans les deux cas la propriété tient. ∎

#Récursion ou itération ?

Toute récursion structurelle se traduit en boucle: parcourir la liste avec un for, descendre dans l'arbre avec une pile explicite. La récursion reste préférable quand la structure est elle-même récursive — le code épouse la forme des données, et la preuve épouse la forme du code. Elle coûte en revanche un cadre de pile par niveau: sur une liste de 10 000 éléments, taille récursive dépasse la limite par défaut de Python et lève RecursionError, alors que len ou une boucle ne bronche pas.

pythonpython

1def taille_iterative(L: list) -> int:2    total = 03    for _ in L:                 # invariant : total = nombre d'éléments déjà comptés4        total += 15    return total

Règle pratique: récursion quand la profondeur reste bornée par la hauteur de la structure (arbres équilibrés, expressions de taille raisonnable); itération ou pile explicite quand la structure peut être longue et linéaire.

#Un dernier exemple: la correction d'Euclide

La récurrence structurelle n'est pas réservée aux structures de données: elle prouve aussi les algorithmes numériques. L'algorithme d'Euclide sous forme soustractive, tel qu'il apparaît au cours:

texttext

1function PGCD(a, b)2  if b > a then return PGCD(b, a)3  if b == 0 then return a4  else return PGCD(a - b, b)

Énoncé. Pour tous entiers a, b ≥ 0, l'appel PGCD(a, b) retourne le plus grand commun diviseur de a et b.

Preuve par induction généralisée sur la somme a + b.

Base : a + b = 0, donc a = b = 0. Le premier test échoue, le second réussit et la fonction retourne 0, qui est bien pgcd(0, 0).

Récurrence : soit a + b > 0. Trois cas.

  • Si b > a, l'appel devient PGCD(b, a), dont la somme des arguments est la même. Le contenu du problème est inchangé — le pgcd est symétrique — et l'hypothèse d'induction s'applique.
  • Si b == 0, alors pgcd(a, 0) = a, ce que la fonction retourne.
  • Sinon a ≥ b > 0 et l'appel devient PGCD(a - b, b). La somme des arguments vaut a - b + b = a < a + b: elle a strictement diminué, l'hypothèse d'induction s'applique. Et pgcd(a - b, b) = pgcd(a, b), car tout diviseur commun de a et b divise a - b, et réciproquement tout diviseur commun de a - b et b divise a = (a - b) + b.

Dans les trois cas le résultat est correct. ∎

La variante itérative du même algorithme est celle utilisée dans les exercices du chapitre:

pythonpython

1def pgcd(a: int, b: int) -> int:2    while b:                        # invariant : pgcd(a, b) est constant3        a, b = b, a % b             # b décroît strictement : terminaison4    return a

#Playground

Chargement de l’éditeur...

#Exercices

  1. PGCD. Implémentez pgcd(a, b) par l'algorithme d'Euclide (tant que b non nul: a, b = b, a % b). Vérifiez: pgcd(48, 18) vaut 6.
  2. Fibonacci mémoïsée. Écrivez fib(n) récursive avec un dictionnaire de mémoïsation pour éviter les recalculs. Vérifiez: fib(40) vaut 102334155 et s'exécute instantanément.
  3. Normalisation. Reprenez normalise avec une liste de votre choix et vérifiez l'invariant: min devient 0.0, max devient 1.0.
  4. Décorateur de mesure. Écrivez un décorateur mesure_temps qui affiche la durée d'exécution de la fonction décorée.
  5. Somme de deux listes. Écrivez la fonction récursive qui prend deux listes d'entiers (de longueurs possiblement différentes) et construit la liste des sommes élément par élément. Exemple: L1 = [1, 2] et L2 = [3, 5, 11] donnent [4, 7, 11]. Démontrez ensuite que la longueur du résultat est le maximum des longueurs de L1 et L2.
  6. Multiplication d'une liste. Écrivez la fonction récursive qui multiplie par 3 chaque élément d'une liste de nombres naturels, puis sa version itérative.
  7. Multiplication d'un arbre. Écrivez la fonction récursive qui multiplie par 5 chaque valeur d'un arbre binaire de nombres naturels.
  8. Statistiques d'un arbre. Écrivez les fonctions récursives qui donnent le nombre de nœuds, le nombre de feuilles et la hauteur d'un arbre binaire.
  9. Élagage. Écrivez la fonction récursive qui supprime toutes les feuilles d'un arbre binaire.
  10. Trace d'une fonction mystère. Soit mistery4(n) définie par: si n < 2 retourner 0; si n est pair retourner n + mistery4(n - 2); sinon retourner mistery4(n - 1). Donnez sa signature, son objectif, et sa valeur pour n = 7.
  11. Borne sur le nombre de nœuds. Démontrez par récurrence structurelle qu'un arbre binaire non vide de hauteur h possède au plus 2^(h+1) - 1 nœuds.

#Corrections

Correction: PGCD
pythonpython

1def pgcd(a: int, b: int) -> int:2    while b:3        a, b = b, a % b4    return a5 6print(pgcd(48, 18))   # 6

Invariant: pgcd(a, b) == pgcd(b, a % b) (Euclide), et b décroît strictement, d'où la terminaison.

Correction: Fibonacci mémoïsée
pythonpython

1def fib(n: int, memo: dict = None) -> int:2    if memo is None:3        memo = {}4    if n in memo:5        return memo[n]6    if n < 2:7        return n8    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)9    return memo[n]10 11print(fib(40))   # 102334155

Sans mémoïsation, fib(40) effectue environ 331 millions d'appels; avec, environ 79: chaque valeur est calculée une seule fois. Notez le paramètre par défaut None plutôt qu'un dictionnaire littéral (voir pièges).

Correction: normalisation
pythonpython

1def normalise(valeurs: list[float], eps: float = 1e-9) -> list[float]:2    """Ramène les valeurs dans [0, 1] (invariant: min -> 0.0, max -> 1.0)."""3    m, M = min(valeurs), max(valeurs)4    etendue = max(eps, M - m)5    return [(v - m) / etendue for v in valeurs]6 7print(normalise([2, 10, 6]))

Sortie :

texttext

1[0.0, 1.0, 0.5]
Correction: décorateur de mesure
pythonpython

1import time2from functools import wraps3 4def mesure_temps(func):5    @wraps(func)6    def wrapper(*args, **kwargs):7        debut = time.perf_counter()8        resultat = func(*args, **kwargs)9        duree = (time.perf_counter() - debut) * 100010        print(f"{func.__name__}: {duree:.2f} ms")11        return resultat12    return wrapper13 14@mesure_temps

@wraps conserve le nom et la docstring de la fonction décorée. perf_counter est préféré à time.time pour mesurer des durées.

Correction: somme de deux listes

La fonction doit couvrir quatre cas: les deux listes vides, une seule liste vide (deux fois), et les deux non vides.

pythonpython

1def somme_listes(L1: list[int], L2: list[int]) -> list[int]:2    """Liste des sommes élément par élément ; s'arrête à la plus longue."""3    if L1 == [] and L2 == []:4        return []5    if L2 == []:6        return [L1[0]] + somme_listes(L1[1:], [])7    if L1 == []:8        return [L2[0]] + somme_listes([], L2[1:])9    return [L1[0] + L2[0]] + somme_listes(L1[1:], L2[1:])10 11print(somme_listes([1, 2], [3, 5, 11]))   # [4, 7, 11]

Le troisième appel est celui du cas général; les deux précédents traitent la fin d'une des listes, où l'élément restant est recopié tel quel.

Preuve que taille(somme_listes(L1, L2)) = max(taille(L1), taille(L2)), par récurrence structurelle sur le couple.

Base : L1 = L2 = []. Le résultat est [], donc taille = 0 = max(0, 0). Vrai.

Récurrence : supposons la propriété vraie pour tous les couples de sous-listes. Si L1 = el1 · L1' et L2 = el2 · L2', alors

texttext

1taille(somme(L1, L2)) = 1 + taille(somme(L1', L2'))2                      = 1 + max(taille(L1'), taille(L2'))     (hypothèse de récurrence)3                      = max(1 + taille(L1'), 1 + taille(L2'))4                      = max(taille(L1), taille(L2))

Si L2 = [] et L1 = el1 · L1', alors taille(somme) = 1 + taille(somme(L1', [])) = 1 + max(taille(L1'), 0) = taille(L1) = max(taille(L1), 0). Le cas symétrique est identique. ∎

Correction: multiplication d'une liste par 3
pythonpython

1def mul3(L: list[int]) -> list[int]:2    if L == []:3        return []4    return [L[0] * 3] + mul3(L[1:])5 6def mul3_iteratif(L: list[int]) -> list[int]:7    resultat = []8    for x in L:                 # invariant : resultat = 3 * éléments déjà traités9        resultat.append(x * 3)10    return resultat11 12print(mul3([1, 2, 3]), mul3_iteratif([1, 2, 3]))   # [3, 6, 9] [3, 6, 9]

La version récursive suit la définition de la liste (el · L1); la version itérative parcourt la liste et construit le résultat. Les deux ont le même coût, Θ(n), mais la seconde ne consomme pas de pile.

Correction: multiplication d'un arbre par 5
pythonpython

1def mul5(T):2    """Arbre où chaque valeur est multipliée par 5."""3    if T is None:4        return None5    valeur, g, d = T6    return (valeur * 5, mul5(g), mul5(d))7 8arbre = (1, (2, None, None), (3, (4, None, None), None))9print(mul5(arbre))   # (5, (10, None, None), (15, (20, None, None), None))

La fonction reconstruit un arbre de même forme: le cas de base est l'arbre vide, le cas progressif traite la racine puis délègue aux deux sous-arbres. Le coût est linéaire en nombre de nœuds.

Correction: statistiques d'un arbre
pythonpython

1def nb_noeuds(T) -> int:2    if T is None:3        return 04    valeur, g, d = T5    return 1 + nb_noeuds(g) + nb_noeuds(d)6 7def nb_feuilles(T) -> int:8    if T is None:9        return 010    valeur, g, d = T11    if g is None and d is None:12        return 113    return nb_feuilles(g) + nb_feuilles(d)14 

Les trois fonctions ont la même charpente — cas vide, décomposition du nœud, combinaison des résultats — et seul l'opérateur de combinaison change (+1, 1 pour une feuille, 1 + max). nb_feuilles a deux cas de base: l'arbre vide et la feuille.

Correction: élagage d'un arbre
pythonpython

1def supprime_feuilles(T):2    """Arbre privé de ses feuilles."""3    if T is None:4        return None5    valeur, g, d = T6    if g is None and d is None:7        return None                     # la feuille disparaît8    return (valeur, supprime_feuilles(g), supprime_feuilles(d))9 10arbre = (8, (3, (1, None, None), None), (10, None, None))11print(supprime_feuilles(arbre))   # (8, (3, None, None), None)

La condition d'arrêt est structurelle: un nœud dont les deux enfants sont vides est une feuille et retourne l'arbre vide. Un arbre réduit à une seule feuille devient donc l'arbre vide, ce qui est cohérent: il n'avait que des feuilles.

Correction: trace de mistery4

Signature : mistery4 : entier naturel → entier naturel.

Objectif : la fonction somme les nombres pairs jusqu'à n. Si n est impair, elle délègue à n - 1 (le plus grand pair inférieur ou égal à n) avant d'accumuler.

Trace pour n = 7 :

texttext

1mistery4(7)  -> 7 impair  -> mistery4(6)2mistery4(6)  -> 6 pair    -> 6 + mistery4(4)3mistery4(4)  -> 4 pair    -> 4 + mistery4(2)4mistery4(2)  -> 2 pair    -> 2 + mistery4(0)5mistery4(0)  -> 0 < 2     -> 0

En remontant: 2 + 0 = 2, puis 4 + 2 = 6, puis 6 + 6 = 12. Donc mistery4(7) = 12, qui est bien 2 + 4 + 6.

Correction: borne sur le nombre de nœuds

Énoncé. Un arbre binaire non vide de hauteur h(T) possède au plus 2^(h(T)+1) - 1 nœuds, avec h définie par: h(r) = 0 si T est réduit à sa racine, et h(T) = max(h(TL), h(TR)) + 1 sinon.

Preuve par récurrence structurelle sur T.

Base : T est réduit à sa racine. Alors n(T) = 1 et h(T) = 0, et 2^(0+1) - 1 = 1. Vrai.

Récurrence : T est une racine reliée à deux sous-arbres TL et TR. Par construction,

texttext

1n(T) = n(TL) + n(TR) + 1        et        h(T) = max(h(TL), h(TR)) + 1

Donc h(TL) ≤ h(T) - 1 et h(TR) ≤ h(T) - 1. Pour chaque sous-arbre non vide, l'hypothèse de récurrence donne n(TL) ≤ 2^(h(TL)+1) - 1 ≤ 2^h(T) - 1; pour un sous-arbre vide, n = 0, et l'inégalité 0 ≤ 2^h(T) - 1 tient dès que h(T) ≥ 1, ce qui est le cas ici puisque T n'est pas réduit à sa racine. En sommant:

texttext

1n(T) ≤ (2^h(T) - 1) + (2^h(T) - 1) + 12     = 2 · 2^h(T) - 13     = 2^(h(T)+1) - 1

La borne est atteinte par l'arbre complet, où chaque niveau est entièrement rempli: il compte exactement 2^(h+1) - 1 nœuds. Un arbre de hauteur h qui a moins de nœuds que cette borne est dit dégénéré ou partiel.

#Pièges fréquents

#Valeur par défaut mutable

La valeur par défaut est créée une seule fois, à la définition. Une liste par défaut est donc partagée entre tous les appels:

pythonpython

1def ajoute_mauvais(item, panier=[]):   # anti-pattern2    panier.append(item)3    return panier4 5print(ajoute_mauvais(1))   # [1]6print(ajoute_mauvais(2))   # [1, 2]: le même panier a survécu à l'appel précédent7 8def ajoute_bon(item, panier=None):9    if panier is None:10        panier = []11    panier.append(item)12    return panier13 14print(ajoute_bon(1))   # [1]

Règle: jamais de mutable (list, dict, set) en valeur par défaut; utilisez None et créez l'objet dans le corps.

#Oublier le return

Une fonction sans return retourne None. Le bug classique:

pythonpython

1def aire_mauvaise(w, h):2    print(w * h)        # affiche mais ne retourne rien3 4resultat = aire_mauvaise(3, 4)5print(resultat)         # None

#Quiz

Pourquoi ajoute_mauvais(2) retourne-t-il [1, 2] ?
Pourquoi ajoute_mauvais(2) retourne-t-il [1, 2] ?
Que retourne une fonction sans instruction return ?
Que retourne une fonction sans instruction return ?
Deux obligations d'une récursion correcte ?
Deux obligations d'une récursion correcte ?