Les procédures récursives
Description
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 :
Remerciement toujours à mon plus fidele ami et "maitre" MoonStone alias LeBouffon ( qui n'a rien à voir avec un certain Loiseau de Belgique comme "un " certain tente de supposer :p ) qui m'a aidé à la revision de mes cours, il y'a quelques mois de cela. Que je met aujours'hui ici, comme ça, pour le fun, parce que je l'avais fait sous emmatopiak et que j'ai envie de relancer la machine du laché de codes :p
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 :
Conclusion :
Remerciement toujours à mon plus fidele ami et "maitre" MoonStone alias LeBouffon ( qui n'a rien à voir avec un certain Loiseau de Belgique comme "un " certain tente de supposer :p ) qui m'a aidé à la revision de mes cours, il y'a quelques mois de cela. Que je met aujours'hui ici, comme ça, pour le fun, parce que je l'avais fait sous emmatopiak et que j'ai envie de relancer la machine du laché de codes :p
Codes Sources
A voir également
- Les procédures récursives
- Procédures stockées - Conseils pratiques -SQL
- Fonctions récursives python - Forum Python
- Procédures stockées mysql ✓ - Forum PHP
- Procedures mysql ✓ - Forum SQL
- Sql procedures - Forum SQL
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.