IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

User

[Actualité] Tracer les appels récursifs en Python

Note : 2 votes pour une moyenne de 3,00.
par , 06/02/2023 à 10h25 (15366 Affichages)
I. Introduction

L'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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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.

Nom : classe_arbreappels.png
Affichages : 4484
Taille : 12,6 Ko

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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
appel_enfant = Node("2 -> fibo(3)", parent=appel_parent)

Ajoutant ainsi un nœud à l'arbre des appels :

Nom : ajout_appel.png
Affichages : 4076
Taille : 1,0 Ko

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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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 :

Nom : remontee_appel.png
Affichages : 4072
Taille : 1,7 Ko

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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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 :

Nom : arbre_appels_1.png
Affichages : 4035
Taille : 4,2 Ko



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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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 - Visualiser dans une fenêtre à part
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 :

Nom : arbre_appels.png
Affichages : 3988
Taille : 3,0 Ko

Module complet de test :

Code Python : Sélectionner tout - Visualiser dans une fenêtre à part
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

Envoyer le billet « Tracer les appels récursifs en Python » dans le blog Viadeo Envoyer le billet « Tracer les appels récursifs en Python » dans le blog Twitter Envoyer le billet « Tracer les appels récursifs en Python » dans le blog Google Envoyer le billet « Tracer les appels récursifs en Python » dans le blog Facebook Envoyer le billet « Tracer les appels récursifs en Python » dans le blog Digg Envoyer le billet « Tracer les appels récursifs en Python » dans le blog Delicious Envoyer le billet « Tracer les appels récursifs en Python » dans le blog MySpace Envoyer le billet « Tracer les appels récursifs en Python » dans le blog Yahoo

Mis à jour 21/04/2023 à 20h44 par User

Catégories
Programmation , Python , Algorithmique

Commentaires

  1. Avatar de pcouaillier
    • |
    • permalink
    Très bon tutoriel pour un débutant en python et en programmation.

    En entreprise ou pour des projets personnels, beaucoup de personnes s'arrêtent à ce niveau.

    Je regrette l'absence d'ouverture en fin de billet vers de l'outillage professionnel (profileur et traceur).

    Voici deux exemples d'outils :
    - cProfile : https://docs.python.org/3/library/profile.html
    - opentelemetry-python : https://opentelemetry-python.readthe...l#useful-links
  2. Avatar de User
    • |
    • permalink
    Merci à toi pour le commentaire et les liens
  3. Avatar de f-leb
    • |
    • permalink
    Super

    pour le débutant avec Thonny, tu peux visualiser la pile en exécutant le programme en mode débogage (pas-à-pas) :



    Une nouvelle fenêtre s'ouvre quand tu empiles un nouveau contexte, la fenêtre se ferme quand tu dépiles le contexte. C'est assez visuel
  4. Avatar de User
    • |
    • permalink
    Ah ouais en effet très didactique pour les débutants

    Merci Fabien pour ce complément