Poupées russes et objets sur mesure : récursivité, classes, modules et tests en Python

Ouvre le dossier Photos de ton ordinateur : il contient des images, mais aussi des sous-dossiers, qui contiennent eux-mêmes des images et des sous-dossiers. Pour tout compter, une phrase suffit : « compte les images ici, puis fais pareil dans chaque sous-dossier ». C'est une définition récursive. Et dans ton jeu vidéo, chaque personnage a ses points de vie et ses actions : c'est un objet. Au programme : récursivité, classes, modules et tests.

1. La récursivité : une fonction qui s'appelle elle-même

Une fonction récursive s'appelle elle-même. Elle a toujours deux ingrédients :

• un cas de base, qui renvoie un résultat sans nouvel appel ;
• un appel récursif sur un problème plus petit, qui se rapproche du cas de base.

Premier exemple, la factorielle : 4! = 4 × 3 × 2 × 1 = 24, et plus généralement n! = n × (n − 1)!, avec 0! = 1.

def factorielle(n):
 if n == 0: # cas de base
 return 1
 return n * factorielle(n - 1) # appel récursif

print(factorielle(4)) # affiche 24

Suivons le calcul : factorielle(4) attend 4 × factorielle(3), qui attend 3 × factorielle(2), et ainsi de suite jusqu'à factorielle(0), qui renvoie 1. Python garde ces 5 appels en attente dans la pile d'appels, puis les termine dans l'ordre inverse : 1, 1 × 1 = 1, 2 × 1 = 2, 3 × 2 = 6, et enfin 4 × 6 = 24. Sans cas de base, les appels s'empilent jusqu'à la limite de Python (1000 par défaut) et le programme s'arrête sur une erreur RecursionError.

Deuxième exemple : un mot est un palindrome si sa première et sa dernière lettre sont égales et si ce qui reste au milieu est lui-même un palindrome.

def est_palindrome(mot):
 if len(mot) <= 1: # cas de base
 return True
 if mot[0] != mot[-1]:
 return False
 return est_palindrome(mot[1:-1]) # le mot sans ses extrémités

print(est_palindrome("radar")) # True
print(est_palindrome("robot")) # False

Pour "radar" : r et r sont égales, on recommence avec "ada", puis "d", une seule lettre : gagné.

2. Les classes : fabriquer ses propres objets

Une classe est un plan de fabrication ; chaque objet construit à partir d'elle en est une instance. Un objet regroupe des attributs (ses données) et des méthodes (les fonctions qui agissent sur lui).

class Personnage:
 def __init__(self, nom, pv):
 self.nom = nom # attribut : le nom
 self.pv = pv # attribut : les points de vie

 def subir(self, degats): # méthode
 self.pv = max(0, self.pv - degats)

 def est_vivant(self):
 return self.pv > 0

heros = Personnage("Aya", 30)
heros.subir(12)
print(heros.pv) # 18
print(heros.est_vivant()) # True

L'instruction Personnage("Aya", 30) crée un objet et appelle aussitôt le constructeur __init__, qui remplit ses attributs. Le premier paramètre de chaque méthode, self, désigne l'objet lui-même : heros.subir(12) exécute subir avec self égal à heros. Deux personnages ont chacun leurs propres attributs : blesser l'un ne touche pas l'autre.

3. Les modules : ranger son code

Un module est un simple fichier .py. Enregistre la classe dans jeu.py ; dans un autre fichier du même dossier, la ligne from jeu import Personnage suffit pour l'utiliser. Tu le fais déjà avec import math. Dans jeu.py, place les essais sous la ligne if __name__ == "__main__": : ils s'exécutent quand tu lances jeu.py lui-même, pas quand un autre fichier l'importe.

4. Les tests unitaires : vérifier chaque brique

L'instruction assert condition ne fait rien si la condition est vraie et lève une erreur AssertionError sinon. Un test unitaire vérifie une seule fonction ou méthode sur des cas choisis : le cas de base, un cas courant, un cas limite. Ajoute-les à la suite de factorielle et de Personnage :

def test_factorielle():
 assert factorielle(0) == 1 # le cas de base
 assert factorielle(5) == 120 # un cas courant

def test_subir():
 p = Personnage("Test", 5)
 p.subir(8) # cas limite : plus de dégâts que de PV
 assert p.pv == 0
 assert not p.est_vivant()

test_factorielle()
test_subir()
print("Tous les tests passent")

Relance tes tests après chaque modification, en gardant en tête l'avertissement d'Edsger Dijkstra : un test peut montrer la présence d'un bug, jamais son absence.

À retenir

• Une fonction récursive s'appelle elle-même : il lui faut un cas de base et des appels qui s'en rapprochent ; les appels en attente sont rangés dans la pile d'appels.
• Une classe décrit des objets : attributs (données), méthodes (actions), constructeur __init__ ; self désigne l'objet concerné.
• Un module est un fichier .py qu'on importe avec import ou from … import ….
• Un test unitaire, écrit avec assert, vérifie une fonction sur le cas de base, un cas courant et les cas limites.

★ Pour aller plus loin

Les tours de Hanoï, un casse-tête inventé par le mathématicien Édouard Lucas en 1883, se résolvent par une fonction récursive de quelques lignes : déplacer n disques demande 2ⁿ − 1 mouvements au minimum. Avec 64 disques, à un mouvement par seconde, il faudrait environ 585 milliards d'années !

La récursivité peut coûter cher : la version naïve de la suite de Fibonacci recalcule sans cesse les mêmes valeurs, soit plus de 2,6 millions d'appels pour fib(30). Le décorateur lru_cache du module functools mémorise les résultats déjà calculés : c'est la mémoïsation.

Hors programme, l'héritage : class Mage(Personnage): crée une classe qui reçoit toutes les méthodes de Personnage et peut en redéfinir.

Sources pour creuser

• Numérique et sciences informatiques, Terminale : 24 leçons avec exercices corrigés, Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre et Kim Nguyen (Ellipses).
• Apprendre à programmer avec Python 3, Gérard Swinnen (Eyrolles).
• Le tutoriel officiel de Python en français, sur docs.python.org/fr : chapitres « Modules » et « Classes ».
• Le MOOC « Python 3 : des fondamentaux aux concepts avancés du langage » (Inria) sur fun-mooc.fr.
• YouTube : sur la chaîne Graven - Développement, cherche « Python orienté objet ».