La version récursive
void afficher_arbre_recursivement(struct arbre * a,int decalage) {
int i;
if (a!=NULL) {
for (i=0;i<decalage;i++) {
printf(" ");
}
printf("( début affichage noeud %d)\n",a->valeur_noeud);
afficher_arbre_recursivement(a->fils_gauche,decalage+1);
afficher_arbre_recursivement(a->fils_droit,decalage+1);
for (i=0;i<decalage;i++) {
printf(" ");
}
printf("( fin affichage noeud %d)\n",a->valeur_noeud);
}
}
Vers une dérécursivation
Les étapes nécessaires à la dérécursivation sont :
la compréhension de la récursion,
une analyse fine du type de récursion,
le passage à une version dérécursivée.
La compréhension de la récursion
Tout d'abord, on peut vérifier que la procédure est récursive. De plus, on peut s'assurer en la testant qu'elle est correcte.
On peut remarquer qu'elle n'est pas récursive terminale : une fonction (ou une procédure) récursive terminale ne contient qu'un seul appel récursif et il est la dernière instruction de la fonction (ou de la procédure). Il va donc falloir utiliser une pile de données pour dérécursiver la fonction. Avant d'implémenter cette pile, il est préférable d'attendre l'analyse fine de la récursion.
Il peut être intéressant de comprendre la fonction récursive. Celle-ci réalise un affichage des nœuds d'un arbre. Voici une trace d'exécution :
(~/divers/derecursivation)>derecursivation
( début affichage noeud 10)
( début affichage noeud 20)
( début affichage noeud 0)
( fin affichage noeud 0)
( début affichage noeud 30)
( fin affichage noeud 30)
( fin affichage noeud 20)
( début affichage noeud 40)
( fin affichage noeud 40)
( fin affichage noeud 10)
L'analyse fine de la récursion
Lorsque l'on réalise une analyse plus fine de la récursion, on se rend compte que le bloc d'instructions correspondant à un nœud (à un sous-arbre donné pour être plus précis) est décomposé en deux parties. La première de ces parties est :
for (i=0;i<decalage;i++) {
printf(" ");
}
printf("( début affichage noeud %d)\n",a->valeur_noeud);
La seconde est :
for (i=0;i<decalage;i++) {
printf(" ");
}
printf("( fin affichage noeud %d)\n",a->valeur_noeud);
On peut remarquer dans une trace d'exécution que les deux blocs correspondants à ces deux parties de code sont séparés :
(~/divers/derecursivation)>derecursivation
( début affichage noeud 10)
( début affichage noeud 20)
( début affichage noeud 0)
( fin affichage noeud 0)
( début affichage noeud 30)
( fin affichage noeud 30)
( fin affichage noeud 20)
( début affichage noeud 40)
( fin affichage noeud 40)
( fin affichage noeud 10)
L'effet de cette séparation fait apparaître la nécécessité de stocker dans la pile une variable pouvant prendre deux valeurs : POSITION_DEBUT et POSITION_FIN. Une valeur de POSITION_DEBUT indique que l'on se trouve dans la première partie, une valeur de POSITION_FIN indique que l'on se trouve dans la seconde partie.
La procédure récursive fait varier à chaque appel ses deux paramètres a et decalage. Il est donc nécessaire de les passer tous les deux sur la pile. Dans le cas où la procédure récursive ne modifie qu'un sous-ensemble de ses paramètres, il n'est utile que d'empiler ce sous-ensemble.
Le passage à la version dérécursivée
On sait à présent quels sont les paramètres que l'on aura besoin d'empiler : un pointeur sur le sous-arbre courant, le décalage actuel et la position (pouvant prendre la valeur POSITION_DEBUT ou la valeur POSITION_FIN). On peut à présent programmer les fonctions suivantes :
struct pile * pileCreerVide();,
int pileEstVide(struct pile * p);,
void pileLiberer(struct pile * p);,
void pileEmpiler(struct pile * p,struct arbre * valeur_element,int decalage_element,int position_element);,
void pileDepiler(struct pile *p,struct arbre ** valeur_element,int * decalage_element,int * position_element);.
Voyons à présent la version récursive et la version dérécursivée, et observons les similitudes. void afficher_arbre_recursivement(struct arbre * a,int decalage) {
int i;
if (a!=NULL) {
for (i=0;i<decalage;i++) {
printf(" ");
}
printf("( début affichage noeud %d)\n",a->valeur_noeud);
afficher_arbre_recursivement(a->fils_gauche,decalage+1);
afficher_arbre_recursivement(a->fils_droit,decalage+1);
for (i=0;i<decalage;i++) {
printf(" ");
}
printf("( fin affichage noeud %d)\n",a->valeur_noeud);
}
}
void afficher_arbre_iterativement(struct arbre * a,int decalage) {
struct pile * p;
struct arbre * arbre_element;
int decalage_element;
int position_element;
int i;
p = pileCreerVide();
if (a!=NULL) {
pileEmpiler(p,a,decalage,POSITION_DEBUT);
}
while (!pileEstVide(p)) {
pileDepiler(p,&arbre_element,&decalage_element,&position_element);
if (arbre_element!=NULL) {
if (position_element==POSITION_DEBUT) {
for (i=0;i<decalage_element;i++) {
printf(" ");
}
printf("( début affichage noeud %d)\n",arbre_element->valeur_noeud);
pileEmpiler(p,arbre_element,decalage_element,POSITION_FIN);
pileEmpiler(p,arbre_element->fils_droit,decalage_element+1,POSITION_DEBUT);
pileEmpiler(p,arbre_element->fils_gauche,decalage_element+1,POSITION_DEBUT);
}
else {
for (i=0;i<decalage_element;i++) {
printf(" ");
}
printf("( fin affichage noeud %d)\n",arbre_element->valeur_noeud);
}
}
}
pileLiberer(p);
}
On notera le renommage des variables dans le cas du programme dérécursivé. Cela n'était pas nécessaire.
afficher_arbre_recursivement(a->fils_gauche,decalage+1);
afficher_arbre_recursivement(a->fils_droit,decalage+1);
pileEmpiler(p,arbre_element,decalage_element,POSITION_FIN);
pileEmpiler(p,arbre_element->fils_droit,decalage_element+1,POSITION_DEBUT);
pileEmpiler(p,arbre_element->fils_gauche,decalage_element+1,POSITION_DEBUT);
On notera d'une part l'inversion entre le fils gauche et le fils droit (afin que le fils gauche soit dépilée en premier) et d'autre part l'empilement du nœud courant, en POSITION_FIN et avant l'empilement des deux fils (afin que la fin de la procédure soit exécutée après que le fils gauche et que le fils droit aient été traités.
La version dérécursivée
void afficher_arbre_iterativement(struct arbre * a,int decalage) {
struct pile * p;
struct arbre * arbre_element;
int decalage_element;
int position_element;
int i;
p = pileCreerVide();
if (a!=NULL) {
pileEmpiler(p,a,decalage,POSITION_DEBUT);
}
while (!pileEstVide(p)) {
pileDepiler(p,&arbre_element,&decalage_element,&position_element);
if (arbre_element!=NULL) {
if (position_element==POSITION_DEBUT) {
for (i=0;i<decalage_element;i++) {
printf(" ");
}
printf("( début affichage noeud %d)\n",arbre_element->valeur_noeud);
pileEmpiler(p,arbre_element,decalage_element,POSITION_FIN);
pileEmpiler(p,arbre_element->fils_droit,decalage_element+1,POSITION_DEBUT);
pileEmpiler(p,arbre_element->fils_gauche,decalage_element+1,POSITION_DEBUT);
}
else {
for (i=0;i<decalage_element;i++) {
printf(" ");
}
printf("( fin affichage noeud %d)\n",arbre_element->valeur_noeud);
}
}
}
pileLiberer(p);
}
Les fichiers :