I. IntroductionL'objectif de ce billet est de montrer comment tracer les différents appels d'une fonction récursive à l'aide de marqueurs placés dans le code de la fonction.
On va utiliser pour cela la librairie Python anytree qui va nous permettre de créer et de dessiner un arbre des appels.
Ce traçage des différents appels numérotés et regroupés par niveau sur un arbre permettra ainsi de mieux visualiser leur enchaînement et donc de mieux comprendre le mécanisme mis en œuvre.
Note importante : par la suite on prendra comme exemple la fonction récursive fibo(n) qui renvoie la valeur du nème terme de la suite de Fibonacci.
L'arbre des appels sera affiché sous forme de texte.
II. Module anytree
Il contient entre autre une classe Node permettant de créer une structure d'arbre classique et une autre classe RenderTree pour construire un itérateur et parcourir les nœuds de l'arbre.
II-A. Installation
Pour installer la librairie exécutez simplement la commande :
pip install anytree
II-B. Code exemple
On donne ici quelques lignes de code prises dans la documentation pour mieux comprendre comment utiliser anytree, et comment créer des objets Node ou RenderTree :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 | >>> from anytree import Node, RenderTree >>> udo = Node("Udo") >>> marc = Node("Marc") >>> lian = Node("Lian", parent=marc) >>> print(RenderTree(udo)) Node('/Udo') >>> print(RenderTree(marc)) Node('/Marc') └── Node('/Marc/Lian') |
Par exemple, la ligne de code :
| Code Python : | Sélectionner tout |
lian = Node("Lian", parent=marc)
Permet de créer le nœud enfant lian relié au nœud parent marc.
En l'absence de nœud parent, on crée alors simplement la racine de l'arbre.
Si vous souhaitez avoir plus d'information sur ce module je vous invite à consulter sa documentation.
III. Création de la classe ArbreAppels
Pour tracer les différents appels d'une fonction récursive, il nous faut créer une classe.
Notre classe ArbreAppels comportera un constructeur, c'est-à-dire une méthode particulière __init__() dont le code est exécuté quand la classe est instanciée.
Elle va nous permettre d'initialiser notre arbre et le compteur d'appel au moment de la création de l'objet :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 | class ArbreAppels: def __init__(self, nom_appel): # initialisation des attributs de la classe self.appel_courant = Node("1 -> " + nom_appel) # ajout de la racine (appel courant = appel n°1) self.compteur_appel = 1 # initialisation du compteur d'appel self.traceur_active = True # traçage activé par défaut |
Pour créer l'objet ArbreAppels avec le nom du 1er appel il suffit de faire :
| Code Python : | Sélectionner tout |
1 2 | # création de l'objet ArbreAppels contenant la racine : 1er appel arbre_appels = ArbreAppels("fibo(4)") |
III-A. Méthode ajouter_appel()
Pour ajouter des appels récursifs à notre arbre, nous devons en plus définir une méthode ajouter_appel() :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 | class ArbreAppels: ... def ajouter_appel(self, nom_appel): if self.traceur_active: # si le traçage est activé self.compteur_appel += 1 # incrémentation du compteur d'appel nom_appel = str(self.compteur_appel) + " -> " + nom_appel # texte affiché sur le nœud, par exemple : "2 -> fibo(3)" self.appel_courant = Node(nom_appel, parent = self.appel_courant) # ajout du nœud pour le nouvel appel |
Cette méthode permet donc de créer un nouvel objet Node à partir du nom du nœud et de son parent :
| Code Python : | Sélectionner tout |
appel_enfant = Node("2 -> fibo(3)", parent=appel_parent)
Ajoutant ainsi un nœud à l'arbre des appels :
Ici on ajoute le nœud enfant correspondant à l'appel n°2 de la fonction fibo, au nœud parent correspondant à l'appel n°1.
Cette méthode peut être exécutée juste avant l'appel récursif :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 | def fibo(n): if n<=1: # si n=0 ou n=1 return n # retourne la valeur de n else: # ajout de l'appel fibo(n-1) à l'arbre des appels arbre_appels.ajouter_appel("fibo(" + str(n-1) + ")") fibo_n1 = fibo(n-1) # appel récursif : descente d'un niveau ... |
III-B. Méthode remonter_appel()
Pour remonter les appels dans notre arbre, nous devons aussi ajouter une méthode remonter_appel() :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 | class ArbreAppels: ... def remonter_appel(self): if self.traceur_active: # si le traçage est activé # on pointe désormais sur le nœud parent self.appel_courant = self.appel_courant.parent |
Cette méthode permet donc de remonter d'un niveau dans l'arbre des appels :
Ici on remonte d'un niveau : du nœud enfant 5 -> fibo(0) on passe au nœud parent 3 -> fibo(2).
Elle doit être exécutée juste après l'appel de la fonction récursive :
| Code Python : | Sélectionner tout |
1 2 3 | ...
fibo_n1 = fibo(n-1) # appel récursif : descente d'un niveau
arbre_appels.remonter_appel() # remontée d'un niveau |
III-C. Méthode tracer()
Enfin, pour tracer les appels récursifs sur notre arbre, nous devons aussi ajouter une méthode tracer() qui permet de parcourir et d'afficher les nœuds de l'arbre :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 | class ArbreAppels: ... def tracer(self): # parcours des nœuds de l'arbre depuis la racine for pre, fill, node in RenderTree(self.get_racine()): print("%s%s" % (pre, node.name)) # affiche le préfixe et le nom du nœud |
La fonction affiche un arbre des appels comme celui-ci :
IV. Implémentation de l'arbre des appels
On souhaite maintenant tracer les différents appels récursifs d'une fonction à l'aide de la classe précédente.
Prenons comme exemple le calcul du nème terme de la suite de Fibonacci définie par la relation de récurrence :
Fi = Fi-1 + Fi-2
Avec comme premiers termes :
F0 = 0
F1 = 1
Partant de cette définition, on peut alors écrire une fonction récursive en Python qui évalue le nème terme de cette suite :
| Code Python : | Sélectionner tout |
1 2 3 4 5 | def fib(n): if n <= 1: # si 1er ou 2e terme : n=0 ou n=1 return n # retourne n else: # sinon, appels récursifs basés sur la relation de récurrence return fib(n-1) + fib(n-2) |
Considérons maintenant la variable arbre_appels faisant référence à un objet crée à partir de notre classe :
| Code Python : | Sélectionner tout |
1 2 3 | # création de l'objet ArbreAppels contenant la racine : 1er appel arbre_appels = ArbreAppels("fibo(4)") ... |
On peut alors positionner les marqueurs de début et de fin des appels aux bons endroits dans le code :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def fibo(n): if n<=1: # si n=0 ou n=1 return n # retourne la valeur de n else: # ajout de l'appel fibo(n-1) à l'arbre des appels arbre_appels.ajouter_appel("fibo(" + str(n-1) + ")") fibo_n1 = fibo(n-1) # appel récursif : descente d'un niveau arbre_appels.remonter_appel() # remontée d'un niveau dans l'arbre # ajout de l'appel fibo(n-2) à l'arbre des appels arbre_appels.ajouter_appel("fibo(" + str(n-2) + ")") fibo_n2 = fibo(n-2) # appel récursif : descente d'un niveau arbre_appels.remonter_appel() # remontée d'un niveau dans l'arbre return (fibo_n1 + fibo_n2) # sortie |
Note importante : comme l'instruction return provoque la sortie immédiate de la fonction, si le marqueur indiquant la remontée des appels est positionné juste après un return, il ne sera pas pris en compte.
De plus, on constate que la variable arbre_appels est déclarée à l'extérieur de la fonction fibo. En effet, on peut toujours ensuite faire référence à cette variable dans la fonction si on ne modifie pas sa valeur.
On peut également ajouter une gestion des exceptions à la fonction pour désactiver le traçage des appels dans le cas où une exception est levée :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 | def fibo(n): try: # code de la fonction except Exception as e: # si une exception est levée if arbre_appels.traceur_active: # si le traçage est activé # on désactive le traçage des appels arbre_appels.traceur_active=False # on affiche le message d'erreur print(e) return False |
Testons maintenant notre fonction :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 | # création de l'objet ArbreAppels contenant la racine : 1er appel arbre_appels = ArbreAppels("fibo(4)") # exécute la fonction pour n=4 fibo_n = fibo(4) # trace l'arbre des appels arbre_appels.tracer() |
Le code affiche :
Module complet de test :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | from anytree import Node, RenderTree class ArbreAppels: def __init__(self, nom_appel): # initialisation des attributs de la classe self.appel_courant = Node("1 -> " + nom_appel) # ajout de la racine (appel courant = appel n°1) self.compteur_appel = 1 # initialisation du compteur d'appel self.traceur_active = True # traçage activé par défaut def ajouter_appel(self, nom_appel): if self.traceur_active: # si le traçage est activé self.compteur_appel += 1 # incrémentation du compteur d'appel nom_appel = str(self.compteur_appel) + " -> " + nom_appel # texte affiché sur le nœud, par exemple : "2 -> fibo(3)" self.appel_courant = Node(nom_appel, parent = self.appel_courant) # ajout du nœud pour le nouvel appel def remonter_appel(self): if self.traceur_active: # si le traçage est activé # on pointe désormais sur le nœud parent self.appel_courant = self.appel_courant.parent def get_racine(self): # on renvoie la racine de l'arbre return self.appel_courant.root def tracer(self): # parcours des nœuds de l'arbre depuis la racine for pre, fill, node in RenderTree(self.get_racine()): print("%s%s" % (pre, node.name)) # affiche le préfixe et le nom du nœud def fibo(n): try: if n<=1: # si n=0 ou n=1 return n # retourne la valeur de n else: # ajout de l'appel fibo(n-1) à l'arbre des appels arbre_appels.ajouter_appel("fibo(" + str(n-1) + ")") fibo_n1 = fibo(n-1) # appel récursif : descente d'un niveau arbre_appels.remonter_appel() # remontée d'un niveau dans l'arbre # ajout de l'appel fibo(n-2) à l'arbre des appels arbre_appels.ajouter_appel("fibo(" + str(n-2) + ")") fibo_n2 = fibo(n-2) # appel récursif : descente d'un niveau arbre_appels.remonter_appel() # remontée d'un niveau dans l'arbre return (fibo_n1 + fibo_n2) # sortie except Exception as e: # si une exception est levée if arbre_appels.traceur_active: # si le traçage est activé # on désactive le traçage des appels arbre_appels.traceur_active=False # on affiche le message d'erreur print(e) return False # sortie de l'appel récursif # création de l'objet ArbreAppels contenant la racine : 1er appel arbre_appels = ArbreAppels("fibo(4)") # exécute la fonction pour n=4 fibo_n = fibo(4) # trace l'arbre des appels arbre_appels.tracer() |
V. Conclusion
Après avoir présenté la librairie anytree, nous avons montré comment créer notre classe ArbreAppels à l'aide de ce module.
Enfin, nous avons donné un exemple d'utilisation de cette classe pour tracer les différents appels récursifs de la fonction fibo(n).
Sources
https://anytree.readthedocs.io/en/latest/
https://fr.wikipedia.org/wiki/Suite_de_Fibonacci