Programmation structurée (Python) · L1 · Section 3/11
Fonctions
Progression
#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
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)) # 12Le 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.
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
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.
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.
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) # 13Rè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.
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)) # 120Chaque 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
#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
1Base : [] appartient à Listes2Récursion: si L1 appartient à Listes et n est un entier, alors [n] · L1 appartient à ListesLe 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:
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
1Base : l'arbre vide appartient à AB2Récursion: si g et d appartiennent à AB, alors le nœud (·, g, d) appartient à ABUn 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:
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 = Tnb_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é.
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:
1Base : a appartient à Expr2Récursion: si E1 et E2 appartiennent à Expr, alors E1 * E2 appartient à ExprLa fonction de parcours doit alors distinguer les deux formes possibles de l'argument:
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:
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ù
1p(L) = (c(L1) - 1) + (c(L2) - 1) + 12 = c(L1) + c(L2) - 13 = c(L) - 1La 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ù
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) + 1La 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
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:
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]:
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.
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 totalRè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:
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 devientPGCD(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, alorspgcd(a, 0) = a, ce que la fonction retourne. - Sinon
a ≥ b > 0et l'appel devientPGCD(a - b, b). La somme des arguments vauta - b + b = a < a + b: elle a strictement diminué, l'hypothèse d'induction s'applique. Etpgcd(a - b, b) = pgcd(a, b), car tout diviseur commun deaetbdivisea - b, et réciproquement tout diviseur commun dea - betbdivisea = (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:
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
#Exercices
- 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)vaut6. - 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)vaut102334155et s'exécute instantanément. - Normalisation. Reprenez
normaliseavec une liste de votre choix et vérifiez l'invariant: min devient 0.0, max devient 1.0. - Décorateur de mesure. Écrivez un décorateur
mesure_tempsqui affiche la durée d'exécution de la fonction décorée. - 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]etL2 = [3, 5, 11]donnent[4, 7, 11]. Démontrez ensuite que la longueur du résultat est le maximum des longueurs deL1etL2. - 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.
- Multiplication d'un arbre. Écrivez la fonction récursive qui multiplie par 5 chaque valeur d'un arbre binaire de nombres naturels.
- 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.
- Élagage. Écrivez la fonction récursive qui supprime toutes les feuilles d'un arbre binaire.
- Trace d'une fonction mystère. Soit
mistery4(n)définie par: sin < 2retourner 0; sinest pair retournern + mistery4(n - 2); sinon retournermistery4(n - 1). Donnez sa signature, son objectif, et sa valeur pourn = 7. - Borne sur le nombre de nœuds. Démontrez par récurrence structurelle qu'un arbre binaire non vide de hauteur
hpossède au plus2^(h+1) - 1nœuds.
#Corrections
Correction: PGCD
1def pgcd(a: int, b: int) -> int:2 while b:3 a, b = b, a % b4 return a5 6print(pgcd(48, 18)) # 6Invariant: pgcd(a, b) == pgcd(b, a % b) (Euclide), et b décroît strictement, d'où la terminaison.
Correction: Fibonacci mémoïsée
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)) # 102334155Sans 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
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 :
1[0.0, 1.0, 0.5]Correction: décorateur de mesure
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.
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
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
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
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
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
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 :
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 -> 0En 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,
1n(T) = n(TL) + n(TR) + 1 et h(T) = max(h(TL), h(TR)) + 1Donc 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:
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:
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:
1def aire_mauvaise(w, h):2 print(w * h) # affiche mais ne retourne rien3 4resultat = aire_mauvaise(3, 4)5print(resultat) # None