Algo AB Récursivité

Identification

Infoforall

15 - Récursivité sur les AB


Nous allons nous attarder sur le déroulement des fonctions récursives que vous avez réalisé dans l'activités précédentes.

Logiciel nécessaire pour l'activité : -

Prérequis :

  • Données : Arbre et Arbre Binaire
  • Algos : Parcours d'Arbres
  • Algos : Algorithmes des Arbres Binaires

Evaluation ✎ :

Documents de cours : open document ou pdf

1 - Fonctions d'interface

Rappel :

2e partie de la définition du type abstrait de données ARBRE BINAIRE : son interface

Description de l'interface du type abstrait Arbre présenté

Les fonctions liées aux Noeuds :

  1. nvND(cle:Cle, data:Data) -> Noeud : on crée un nouveau noeud et son élément attaché. Ce n'est pas une fonction d'interface de l'arbre mais on a besoin au moins de pouvoir créer un Noeud.
  2. cle(noeud:Noeud) -> Cle : renvoie la clé ou l'étiquette du noeud.
  3. data(noeud:Noeud) -> Data : renvoie les données associées au noeud.

Les fonctions liées à l'Arbre Binaire lui-même :

  1. nvAV() -> Arbre : on le note ainsi pour dire nouvelArbreVide : on crée un nouvel ARBRE BINAIRE vide.
  2. nvAB(r:Noeud, g:Arbre, d:Arbre) -> Arbre : on crée un nouvel ARBRE BINAIRE dont la racine est r et dont les sous-arbres sont g et d fournis.
  3. estArbreVide(arbre:Arbre) -> bool : True si l'arbre est un arbre vide.
  4. racine(arbre:Arbre) -> Noeud : renvoie le noeud jouant le rôle de la racine pour cet arbre.
  5. gauche(arbre:Arbre) -> Arbre : renvoie le sous-arbre gauche de arbre. On obtient bien un Arbre. Si vous voulez le noeud gauche, il faudra appliquer en plus la fonction racine.
  6. droite(arbre:Arbre) -> Arbre : renvoie le sous-arbre droit de arbre.

Dans toute l'activité, nous travaillerons avec cet Arbre Binaire :

1 2 3 4 5 6 7 8
ad = nvAB(nvND("D")) af = nvAB(nvND("F")) ae = nvAB(nvND("E"), g=ad), d=af) ah = nvAB(nvND("H")) ag = nvAB(nvND("G"), d=ah) ab = nvAB(nvND("B")) ac = nvAB(nvND("C"), g=ag, d=ab) aa = nvAB(nvND("A"), g=ac, d=ae)
Arbre qui sera utilisé pendant cette activité : celui décrit sur le code ci-dessus

Nous ne reviendrons plus sur les trois façons de parcourir un Arbre Binaire en profondeur. Voici simplement les trois exemples pour lequel l'exploration se résume à un simple affichage de la clé ou de l'étiquette des noeuds :

1 2 3 4 5 6
def parcours_prefixe(arbre:Arbre) -> None: '''Exploration (et affichage) en profondeur en préfixe RGD''' if not estArbreVide(arbre): print(cle(racine(arbre))) parcours_prefixe(gauche(arbre)) parcours_prefixe(droite(arbre))
1 2 3 4 5 6
def parcours_postfixe(arbre:Arbre) -> None: '''Exploration (et affichage) en profondeur en postfixe GDR''' if not estArbreVide(arbre): parcours_postfixe(gauche(arbre)) parcours_postfixe(droite(arbre)) print(cle(racine(arbre)))
1 2 3 4 5 6
def parcours_infixe(arbre:Arbre) -> None: '''Exploration (et affichage) en profondeur en infixe GRD''' if not estArbreVide(arbre): parcours_infixe(gauche(arbre)) print(cle(racine(arbre))) parcours_infixe(droite(arbre))

2 - Chercher la hauteur de l'Arbre Binaire

Comment parvenir à retrouver le code de la fonction récursive qui permet de déterminer la hauteur de l'Arbre Binaire ?

En se demandant déjà quels sont les cas d'arrêt.

Si l'Arbre Binaire est un arbre vide, on peut répondre : la hauteur est

  • 0 si on prend pour une profondeur de 1 pour la racine.
  • -1 si on prend une profondeur de 0 pour la racine.

Et dans les autres cas, on peut pas répondre immédiatement. On faut relancer des appels récursifs.

On peut juste répondre que la hauteur de l'arbre est soit

  • 1 + la hauteur du sous-arbre gauche ou
  • 1 + la hauteur du sous-arbre droite.

On dira alors que le cas récursif doit répondre 1 + la plus grande de deux hauteurs à gauche et à droite.

Version Python

1 2 3 4 5 6
def hauteur(arbre:Arbre, profondeur_vide=-1) -> int: '''Renvoie la hauteur de l'Arbre Binaire''' if estArbreVide(arbre): return profondeur_vide else: return 1 + max(hauteur(gauche(arbre)), hauteur(droite(arbre)))

Exemple graphique hyper détaillé avec la recherche de la hauteur de l'Arbre ag.

On cherche la hauteur à partir de la racine G. Ce n'est pas un arbre binaire vide. L'appel à la fonction va renvoyer :

hauteur(ag) va renvoyer 1 + max(hauteur(gauche(ag)), hauteur(droite(ag))), ou simplement

hauteur(ag) va renvoyer 1 + max(hauteur(arbre vide), hauteur(ah)).

1er appel

On doit donc faire deux appels recursifs pour obtenir la réponse :

hauteur(arbre vide) renvoie -1, un cas de base, une réponse définitive.

2e appel

hauteur(ah) va renvoyer 1 + max(hauteur(arbre vide), hauteur(arbre vide)).

3e appel

Les deux appels sur un arbre vide font répondre -1.

4e et 5e appel

On peut maintenant dépiler : nous avons toutes nos réponses :

hauteur(ah) renvoie 1 + max(-1, -1).

hauteur(ah) renvoie 1 + -1.

hauteur(ah) renvoie 0.

On peut donc remonter d'un cran :

hauteur(ag) va renvoyer 1 + max(hauteur(arbre vide), hauteur(ah)).

hauteur(ag) renvoie 1 + max(-1, 0).

hauteur(ag) renvoie 1 + 0.

hauteur(ag) renvoie 1.

Réponse finale

Comment rédiger cela sans y passer 15 minutes ? Deux façons de faire :

  1. Noter les appels et réponses sur le schéma
  2. Noter les appels récursifs en laissant un peu de place : de cette façon, on pourra noter les résultats en dessous au fur et à mesure des réponses définitives lors d'un dépilement.

Exemple de rédaction de réponse si on vous demande des justifications :

On écrit les appels dans l'ordre d'apparition :

Réponse finale : empilement

Ensuite, on rajoute les réponses lorsqu'elles arrivent lors du dépilement.

Réponse finale : etape 2

Il suffit alors de compléter votre rédaction au fur et à mesure des réponses qu'on parvient à obtenir.

Réponse finale : etape 3

Au final, on aura alors quelque chose qui ressemble à cela :

Réponse finale : etape 4

01° Réaliser l'empilement des appels récursifs de la fonction hauteur sur l'arbre de racine A, qu'on notera aa. Fournir ensuite la réponse finale que va renvoyer la fonction.

Arbre exercice
1 2 3 4 5 6
def hauteur(arbre:Arbre, profondeur_vide=-1) -> int: '''Renvoie la hauteur de l'Arbre Binaire''' if estArbreVide(arbre): return profondeur_vide else: return 1 + max(hauteur(gauche(arbre)), hauteur(droite(arbre)))

...CORRECTION...

L'empilement provoque des appels à ces fonctions :

Correction question 1

Il reste à dépiler en allant chercher les réponses au fur et à mesure :

Correction question 1-b

On continue :

Correction question 1-c

On peut alors maintenant avoir notre réponse :

Correction question 1-d

02° Réaliser l'empilement des appels récursifs de la fonction hauteur sur l'arbre aa. Fournir ensuite la réponse finale que va renvoyer la fonction.

Arbre de la partie 1

...CORRECTION...

03° En utilisant uniquement les fonctions d'interface (et sans regarder le code), retrouver le code de la fonction récursive hauteur.

Pour cela, demandez-vous quel est (ou sont) le (ou les) cas de base qui permettent de répondre immédiatement. Réflechir ensuite à la réponse qu'on peut fournir dans le cas récursif.

3 - Recherche recursive de la taille de l'Arbre Binaire

La taille correspond au nombre de noeuds.

04° Fournir le code d'une fonction taille où le seul cas de base est l'arbre vide : on doit renvoyer 0 puisqu'il ne contient pas de noeud.

...CORRECTION...

1 2 3 4 5 6
def taille(arbre:Arbre) -> int: '''Renvoie la taille de l'Arbre Binaire''' if estArbreVide(arbre): return 0 else: return 1 + taille(gauche(arbre)) + taille(droite(arbre))

05° Fournir le code d'une fonction taille qui possède deux cas de base : l'arbre vide (on renvoie 0) et la feuille (on renvoie 1).

...CORRECTION...

1 2 3 4 5 6 7 8
def taille(arbre:Arbre) -> int: '''Renvoie la taille de l'Arbre Binaire''' if estArbreVide(arbre): return 0 elif estArbreVide(gauche(arbre)) and estArbreVide(droite(arbre)): return 1 else: return 1 + taille(gauche(arbre)) + taille(droite(arbre))

06° Réaliser l'empilement des appels récursifs de la fonction taille sur l'arbre de racine A, qu'on notera aa. Fournir ensuite la réponse finale que va renvoyer la fonction. On prendra l'algorithme à deux cas de base pour limiter les appels récursifs : sur le cas d'une feuille, on peut répondre immédiatement.

Arbre exercice

...CORRECTION...

Correction question 6

07° Réaliser l'empilement des appels récursifs de la fonction taille sur l'arbre aa. Fournir ensuite la réponse finale que va renvoyer la fonction. On prendra l'algorithme à deux cas de base pour limiter les appels récursifs : sur le cas d'une feuille, on peut répondre immédiatement.

Arbre de la partie 1

...CORRECTION...

4 - Recherche récursive

Voyons également comment trouver un noeud possèdant une valeur de clé-étiquette précise ou un noeud n'ayant que des sous-arbres vides (une feuille donc).

08° Que doit renvoyer la fonction récursive nb_f qui compte les feuilles sur le cas de base "Arbre Vide" ? Sur le cas de base "Feuille" ? Comment tester qu'un arbre est en réalité constitué uniquement d'une feuille ?

Fournir alors le code de la fonction récursive nb_f.

...CORRECTION...

Si l'arbre est vide : on renvoie 0.

Si l'arbre est constitué uniquement une feuille : on renvoie 1.

L'arbre est constitué d'une feuille si les sous-arbres gauche et droite sont des arbres vides.

Sinon, c'est le cas récursif : on renvoie la somme de l'appel de cette fonction à gauche et de l'appel à droite.

1 2 3 4 5 6 7 8
def nb_f(arbre:Arbre) -> int: '''Renvoie le nombre de feuilles de l'Arbre Binaire''' if estArbreVide(arbre): return 0 elif estArbreVide(gauche(arbre)) and estArbreVide(droite(arbre)): return 1 else: return nb_f(gauche(arbre)) + nb_f(droite(arbre))

09° Réaliser l'empilement des appels récursifs de la fonction nb_f sur l'arbre de racine A, qu'on notera aa. Fournir ensuite la réponse finale que va renvoyer la fonction.

Arbre exercice

...CORRECTION...

Correction question 9

10° Réaliser l'empilement des appels récursifs de la fonction nb_f sur l'arbre aa. Fournir ensuite la réponse finale que va renvoyer la fonction.

Arbre de la partie 1

...CORRECTION...

11° Réaliser la fonction booléenne estPresent. Elle doit renvoyer True si la clé fournie apparaît bien dans l'Arbre Binaire.

  • Condition d'arrêt 1 : l'arbre est vide.
  • Cas de base : on renvoie False
  • Condition d'arrêt 2 : la clé de la racine a la bonne valeur.
  • Cas de base : on renvoie True
  • Cas récursif :
  • On renvoie le résultat de la recherche sur l'arbre gauche OU de la recherche dans l'arbre droite.

Question subsidiaire : que renvoie un OU s'il l'un des termes est VRAI ?

1 2 3
def estPresent(arbre:Arbre, c:Cle) -> bool: '''Fonction booléenne : True si c est la clé d'un des noeuds''' pass

...CORRECTION...

1 2 3 4 5 6 7 8
def estPresent(arbre:Arbre, c:Cle) -> bool: '''Fonction booléenne : True si c est la clé d'un des noeuds''' if estArbreVide(arbre): return False elif cle(racine(arbre)) == c: return True else: return estPresent(gauche(arbre), c) or estPresent(droite(arbre), c)

12° Réaliser l'empilement des appels récursifs de la fonction estPresent sur l'arbre de racine A en rechant la clé "B". Fournir ensuite la réponse finale que va renvoyer la fonction. N'oubliez pas que le OU et le ET sont paresseux en Python.

Arbre exercice

...CORRECTION...

Correction question 12

13° Réaliser l'empilement des appels récursifs de la fonction estPresent sur l'arbre de racine A en rechant la clé "C". Fournir ensuite la réponse finale que va renvoyer la fonction. N'oubliez pas que le OU et le ET sont paresseux en Python.

Arbre exercice

...CORRECTION...

Correction question 13

5 - FAQ

Rien pour le moment

Il nous reste encore à voir le parcours en largeur puis un type particulier d'Arbre Binaire : l'Arbre Binaire de Recherche.

Activité publiée le 13 12 2020
Dernière modification : 13 12 2020
Auteur : ows. h.