Kha-tastrophe.net

Le site kha-tastrophique de Kha

> Cours > Informatique> Algorithmique et Analyse > Récursion

6. Récursion

6.1. Définition

Illustration de la récursion : les pendentifs de la vache qui rit

On dit qu'une procédure est récursive lorsque dans le corps de cette procédure il y a une appel à cette procédure elle-même (récursion directe) ou un appel à une autre procédure qui à son tour appelle la première (récursion indirecte).

La célèbre tête de vache dans le médaillon porte aux oreilles deux pendentifs, dans chacun figure une tête de vache qui porte aux oreilles deux pendentifs où figure ...

Ce procédé, connu sous le nom de "mise en abyme", a été utilisé par certains peintres et écrivains, il constitue un exemple flagrant de processus récursif.

L'exemple le plus connu est la fonction "factorielle". la première fois qu'on la rencontre en mathématique, elle est engendrée par n! = 1.2.3.4...n (n étant un entier naturel) ; par la suite, on préfère une définition plus élégante1 n! = n.(n-1) qui n'a de sens que si elle est assortie de 0! = 1. En voici la traduction en notations algorithmiques :

1. La question est de savoir si la notion de récursion est plus ou moins naturelle que la notion d'itération ne relève pas de notre propos ; l'expérience semble seulement nous prouver que nombre d'étudiants rencontrent "certaines difficultés" lors de son étude.

fermer cette précision

fonction factorielle (n)
    si n Symbole : inférieur et égal 1 alors
        factorielle Symbole : affectation 1
    sinon
        factorielle Symbole : affectation n * factorielle (n-1)
    fin_si
fin_fonction factorielle

6.2. Conditions

Il faut, lorsqu'on veut écrire une procédure récursive, avoir l'assurance que le nombre d'appels récursifs sera fini (tout comme le nombre d'étapes d'itération lors de l'écriture d'une boucle!). Sans vouloir s'intéresser aux cas trop pathologiques on peut dire, en simplifiant, que l'écriture d'une procédure récursive nécessite que, lors des appels successifs, le domaine des arguments aille en retrécissant, convergeant vers une limite qui corresponde au test d'arrêt des appels récursifs.

Sur un plan pratique, pour que le code engendré puisse être récursif il doit, pour chaque appel de la procédure :

  • mémoriser l'adresse de retour,
  • créer un nouveau jeu de variables locales à cette procédure, ces variables étant les seuls "visibles" pendant une éxecution (et, bien sûr, cessant d'être visibles après la fin d'éxecution ou si cette éxecution engendre un nouvel appel de procédure qui fait quitter provisoirement la procédure active) ; on désigne ce jeu de variables locales par le terme "environnement".

Un tel fonctionnement peut facilement être réalisé sur une machine à pile2 où les zones de travail de chaque procédure sont allouées en "pile" (cf. le "stack frame" évoque en 2.2), une seule zone étant utilisée à la fois.

2. On illustre dans l'Appendice 6.5 comment se réalisent les appels de procédure sur la machine SPARC étudiée par ailleurs.

fermer cette précision

6.3. Exemple : traversée d'un arbre

Nous rappelons, en la développant, la procédure esquissée au chapitre précédent : en particulier, nous créons des variables locales p, f_g, f_d (bien qu'elles ne soient pas strictement nécessaires) afin de mieux pouvoir illustrer, lors des appels, le stockage des variables locales.

procédure parcourir_rameau (p_rameau : pointeur sur t_noeud, Entrée;         /* pointe sur la racine */ )
    /* parcours "infixe" version récursive */
    p, f_g, f_d : pointeurs sur t_noeud, variables locales;
    p Symbole : affectation p_rameau
    f_g Symbole : affectation f_gauche (p);
    f_d Symbole : affectation f_droit (p);
    si f_g Symbole : différent NIL alors
        parcourir_rameau (f_g)       prochaine action à faire en revenant du rameau f_g : "imprimer" la clé
    fin_si
    imprimer clé(p)
    si f_d Symbole : différent NIL alors
        parcourir_rameau (f_d)       par contre, en revenant du rameau f_d, il n'y a rien d'autre à faire que de terminer la procédure, donc : "return"
    fin_si
fin_procédure parcourir_rameau

Simulation de la traversée d'un arbre

Simulation de la traversée d'un arbre

On va simuler le fonctionnement de cette procédure et examiner au cours du temps le déroulement des appels et les valeurs des jeux de variables pour l'arbre ci-dessus.

Simulation de l'exécution récursive (allocation de "stack frames")

Simulation de l'exécution récursive (allocation de stack frames)

Dans le schéma ci-dessus, on a représenté :

  • horizontalement, le temps qui correspond aux différentes étapes du déroulement des procédures ;
  • verticalement, l'allocation des "stack frames" et les valeurs successives des différents jeux de variables p, f_g, f_d (on a ajouté la variable P_A qui sert à mémoriser la "prochaine action" à réaliser).

Lors de chaque appel à parcourir_rameau, la valeur de l'argument d'appel a été encadrée.

6.4. Méthode de "dérécursification"

Nous allons nous intéresser à la transformation d'algorithmes récursifs en algorithmes itératifs.

Il existe des algorithmes permettant d'automatiser cette transformation.

On peut aussi réaliser la transformation d'un algorithme récursif en un algorithme itératif en examinant les "actions" effectuées par le processeur lors de l'éxecution de l'algorithme récursif et en simulant ce fonctionnement à l'aide d'un automate très simple (à un seul état). Les principales difficultés sont rassemblées dans la simulation de la séquence d'appel de la procédure, il faut :

  • transférer les arguments entre appelant et appelé simulés,
  • mémoriser la valeur du compteur ordinal simulé (afin de pouvoir reprendre ultérieurement le traitement à l'endroit où il avait été interrompu),
  • allouer l'espace pour les variables locales à cette nouvelle instance de la procédure ; cette allocation est simulée en stockant dans une pile les valeurs des variables locales juste avant l'appel et en réutilisant ces variables avec de nouvelles valeurs résultant de l'appel,
  • lorsqu'une instance de procédure simulée s'achève, il faut rétablir les variables locales en cours avant l'appel (en dépilant les valeurs stockées) puis rétablir la valeur du compteur ordinal simulé pour reprendre le traitement interrompu.

6.4.1. Liste des actions

En examinant le texte de la procédure récursive, on dresse la liste des différentes actions réalisées (elles constituent, en quelque sorte, le jeu d'instructions exécutables par le processeur dont on va simuler le fonctionnement) :

procédure parcourir_rameau (p_rameau : pointeur sur t_noeud, Entrée          /* pointe sur la racine */ )
/* on suppose p_rameau Symbole : différent NIL */
p, f_g, f_d : pointeurs sur t_noeud, variables locales;
p Symbole : affectation p_rameau							action = débuter
f_g Symbole : affectation f_gauche(p)
f_d Symbole : affectation f_droit(p)	
si f_g Symbole : différent NIL alors
	parcourir_rameau(f_g)					action = appeler "parcourir rameau"
fin_si
imprimer clé(p)							action = imprimer
si f_d Symbole : différent NIL alors
	parcourir_rameau(f_d)					action = appeler "parcourir rameau"
fin_si
fin_procédure parcourir_rameau					action = terminer

Procédure récursive : étude des actions (Formalisation)

Type
    ty_action = (débuter, appeler, imprimer, terminer)
fin_type ty_action

6.4.2. Moteur d'automate

Au cours de l'exécution de chaque action, on détermine l'action qui devra être exécutée "juste après" (c'est ce que nous appelerons "action courante" A_C).

Voici le squelette du "moteur d'automate" qui simule un processeur :

variable locale
    A_C : ty_action /* "action courante" c.-à-d. à exécuter immédiatement */

    répéter
        si              A_C = débuter               alors
            ...
        sinon si        A_C = imprimer              alors
            ...
        sinon si        A_C = appeler               alors
            ...
        sinon si        A_C = terminer              alors
            ...
    fin_répéter

6.4.3. Simulation de la séquence d'appel

Dans la réalité le programme appelant détermine, avant chaque appel, les valeurs des arguments d'appel ; la procédure appelée récupère les arguments d'appel et réalise le traitement prévu.

Notre procédure (dérécursifiée) simule l'exécution d'une procédure qui s'appelle elle-même ; on est donc appelé à simuler, à la fois, ce qui se passe à l'extérieur de la procédure (séquence d'appel) et à l'intérieur (récupération des arguments). Dans le cas étudié ici, la procédure n'a qu'un seul argument, un pointeur vers la racine du sous-arbre à parcourir : nous avons appelé p_call la valeur de ce pointeur établie au moment de l'appel ("à l'extérieur" de la procédure) ; nous avons appelé p l'argument correspondant manipulé "à l'intérieur" de la procédure. Donc avant chaque appel simulé il faut déterminer la valeur de p_call et, lors du début de l'exécution correspondante, il faut recopier la valeur de p_call dans la variable p "interne" à la procédure simulée.

Lorsque, dans la réalité, l'instruction exécutée est un appel de procédure, le processeur stocke (au moment du saut) l'adresse de l'instruction du programme appelant qui sera exécutée immédiatement après la fin de la procédure appelée. Nous allons simuler ce mécanisme en stockant avant chaque appel simulé, la "prochaine action" (c.-à-d. l'action qui doit être exécutée lorsque la procédure dont on simule l'appel aura fini de s'exécuter) dans la variable P_A.

Variables locales utilisées au passage entre appels simulés

p_call : pointeur vers ty_noeud, variable locale,                         simule l'argument d'appel
P_A : ty_action, /* action à exécuter après que A_C a été achevée */      simule le stockage de la valeur du compteur ordinal au moment de l'appel

6.4.4. Simulation du "stack-frame"

C'est une structure de pile qu'on implémente dans un tableau d'agrégats. Chaque élément de la pile contiendra un environnement c.-à-d. les variables locales et la "prochaine action". Cette structure de pile est gérée par des procédures calquées sur les prototypes du chapitre 2 : Empiler, Dépiler, Init_Pile.

Définition de l'environnement et de la pile

Type ty_environnement = agrégat
    p, f_g, f_d : pointeurs sur ty_noeud;
    P_A : ty_action
fin_agrégat ty_environnement

Type ty_pile_de_récursion = agrégat
    t_environnement : tableau de ty_environnement indice[1..prof_max];
    prof : indice pour t_environnement
fin_agrégat ty_pile_de_récursion

6.4.5. Détail des actions

En supposant que tout a été initialisé, on peut écrire chaque action :

action débuter

p Symbole : affectation p _call     /* suppose p_call Symbole : différent NIL */
f_g Symbole : affectation f_gauche(p)
f_d Symbole : affectation f_droit(p)
p_call Symbole : affectation f_g
P_A Symbole : affectation imprimer
A_C Symbole : affectation appeler

action imprimer

imprimer clé(p)
p_call Symbole : affectation f_d
P_A Symbole : affectation terminer
A_C Symbole : affectation appeler

action appeler

si p_call Symbole : différent NIL alors
    Empiler (p, f_g, f_d, P_A)      ce n'est pas la syntaxe complète
    A_C Symbole : affectation débuter
sinon
    A_C Symbole : affectation P_A
fin_si

action terminer

variable locale OK : booléen /* rend compte de la bonne exécution de "Dépiler" */
    Dépiler (p, f_g, f_d, P_A, OK)
    si OK alors
        A_C Symbole : affectation P_A
    sinon       la pile était vide, ce qui signifie qu'on a fini de traiter tous les appels
        return      donc quitter la procédure parcourir_rameau
    fin_si

6.4.6. Procédure itérative Parcourir_rameau

Assemblons et complétons tout ce qui précède :

procédure itérative Parcourir_rameau

procédure parcourir_rameau (p_rameau : pointeur sur ty_noeud, Entrée         /* version itérative */ /* pointe sur la racine */
    Types
        ty_action = (débuter, appeler, imprimer, terminer)
            fin_type ty_action
        ty_environnement = agrégat
                p, f_g, f_d : pointeurs sur ty_noeud;
                P_A : ty_action
            fin_type ty_environnement
        ty_pile_de_récursion = agrégat
                t_environnement : tableau de ty_environnement indice[1..prof_max];
                prof : indice pour t_environnement
            fin_type ty_pile_de_récursion
    variables locales
            environnement_courant : ty_environnement; /* p, f_g, f_d, P_A */
                    /* P_A simule le stockage de la valeur du compteur ordinal au moment de l'appel */
            stack_frame : ty_pile_de_récursion
        A_C : ty_action /* "action courante" c.-à-d. à exécuter immédiatement */
        p_call : pointeur vers ty_noeud, variable local, simule l'argument d'appel
        OK : booléen /* rend compte de la bonne exécution de "Dépiler" */
        on travaille avec environnement_courant
    si p_rameau Symbole : différent NIL alors
        Init_Pile (stack_frame)
        p_call Symbole : affectation p_rameau
        A_C Symbole : affectation débuter
        répéter
            si A_C = débuter alors
                p Symbole : affectation p_call
                f_g Symbole : affectation f_gauche(p)
                f_d Symbole : affectation f_droit(p)
                p_call Symbole : affectation f_g
                P_A Symbole : affectation imprimer
                A_C Symbole : affectation appeler        /* fin_cas A_C = débuter */
            sinon si A_C = imprimer alors
                imprimer clé(p)
                p_call Symbole : affectation f_d
                P_A Symbole : affectation terminer
                A_C Symbole : affectation appeler     /* fin_cas A_C = imprimer */
            sinon si A_C = appeler alors
                si p_call Symbole : différent NIL alors
                    Empiler (environnement_courant)      syntaxe!
                    A_C Symbole : affectation débuter
                sinon
                    A_C Symbole : affectation P_A
                fin_si      /* fin_cas A_C = appeler */
            sinon si A_C = terminer alors
                Dépiler (environnement_courant, OK)
                si OK alors
                    A_C Symbole : affectation P_A
                sinon       la pile est vide, ce qui signifie qu'on a fini de traiter tous les appels
                    return      quitter la boucle et la procédure
                fin_si      /* fin_cas A_C = terminer */
            fin_si      /* choix des actions */
        fin_répéter
    fin_si /* p_rameau Symbole : différent NIL */
fin_procédure parcourir_rameau

6.5. Procédure récursive ou itérative

La question que l'on pose souvent est celle-là.

Oublions l'apsect historique : pendant longtemps les langages dominants (FORTRAN, COBOL) n'ont pas permis la récursion. Au moins en ce qui concerne FORTRAN, cette époque est révolue3 : la norme 90 permet la récursion et nombre de compilateurs FORTRAN 77 actuels supportent en tant qu'extension par rapport à la norme.

3. Cependant dans les traités et les bibliothèques de programme, il existe encore de nombreux exemples de programmes et d'algorithmes dont la nature récursive a été masquée par l'emploi de tableaux destinés à simuler un fonctionnement de pile, sans que cette dérécursification soit clairement énoncée.

fermer cette précision

Nous proposerons quelques règles simples :

  • lorsque la solution d'un problème est a priori de type récursif, et cela est en général lié à la structure essentielle4 des données manipulées, il est normal - et efficace - de programmer une solution récursive,
  • si le programme doit être utilisé intensivement et si la fonction récursive est située dans la partie la plus active et si la profondeur des récursions est importante (ou si la taille des variables locales est très grande), alors il peut être intéressant de dérécursifier la solution...

4. Un parcours d'arbre peut avoir lieu sans qu'il y ait explicitement de structures de données de type arbre, par exemple une recherche dichotomique, ou encore une recherche avec des marches arrière ("back tracking").

fermer cette précision

Il faut noter que :

  • si la récursion est "terminale", c.-à-d. si l'appel récursif est la dernière instruction de la procédure5, alors la transformation en itération est aisée (et ne nécessite pas l'utilisation de pile). Cette remarque peut être illustrée à l'aide de l'algorithme que nous venons d'écrire : on définirait une action supplémentaire, appel_terminal, semblable à appeler à ceci près qu'elle ne réaliserait pas Empiler, l'action imprimer serait modifiée : A_C Symbole : affectation appel_terminal,
  • la dérécursification permet aussi de pratiquer une sauvegarde sélective des variables locales, en évitant de sauver les variables qui n'ont pas d'usage par la suite (ce qui est le cas de f_g dans notre exemple).

5. Si le problème le permet, il peut être avantageux de rejeter en appel récursif terminal la récursion qui aurait entraîné le plus d'appels récursifs (nous verrons plus loin un exemple dans la procédure "QuickSort").

fermer cette précision

6.6. Appendice : appel de procédure et gestion de la mémoire

6.6.1. Langage FORTRAN

Diagramme illustrant l'activation succesive des différentes unités d'un programme

Langage FORTRAN : diagramme illustrant l'activation succesive des différentes unités d'un programme

Les flèches indiquent les changements de procédure active et les instructions concernées, les différentes colonnes correspondent au déroulement du temps.

N.B. Le code du programme n'existe qu'à un seul exemplaire et les duplications des codes dans les boîtes ci-dessus n'ont été faites que pour faciliter l'identification des éléments des procédures concernées (le code complet : programme plus sous-programme) figure dans la colonne de gauche.

Allocation des "stack frames" propres à chaque procédure,
(chaque stack frame contient entre autres, les variables locales à la procédure correspondante

Langage FORTRAN : allocation des stack frames propres à chaque procédure

N.B. La pile croît vers le bas ; en grisé les éléments de pile temporairement inaccessibles, en hachuré la zone mémoire inutilisée.

Fenêtre des registres "visibles" par la procédure active
(diagramme spécifique à une machine SPARC, le contenu des registres correspond au cas du programme FORTRAN)

Langage FORTRAN : fenêtre des registres visibles par la procédure active

On a supposé que, à l'entrée dans chaque procédure, l'instruction SAVE est exécutée et que RESTORE est exécutée à la sortie ; les valeurs des registres %O sont celles au moment de l'appel de la procédure fille ; le caractère @ est l'abréviation usuelle de "adresse de".

On a montré, en regard du déroulement d'un programme, les allocations des "stack frame" dans lesquels sont implantées les variables locales.

Dans le cas de FORTRAN on a rappelé, en outre, comment étaient utilisés les registres pour communiquer les arguments et mémoriser les paramètres caractéristiques de l'exécution de chaque procédure.

6.6.2. Langage C

Diagramme illustrant l'activation successive des différentes unités d'un programme

Langage C : diagramme illustrant l'activation successive des différentes unités d'un programme

Les flèches indiquent les changements de procédure active et les instructions concernées, les différentes colonnes correspondent au déroulement du temps.

N.B. Le code du programme n'existe qu'à un seul exemplaire et les duplications des codes dans les boîtes ci-dessus n'ont été faites que pour faciliter l'identification des éléments des procédures concernées (le code complet : programme et sous-programme) figure dans la colonne de gauche.

Allocation des "stack frames" propres à chaque procédure,
(chaque stack frame contient entre autres, les variables locales à la procédure correspondante)

Langage C : allocation des stack frames propres à chaque procédure

N.B. La pile croît vers le bas ; en grisé les éléments de pile temporairement inaccessibles, en hachuré la zone mémoire inutilisée.