> Quelques cours > Algorithmique et Analyse > 6. Récursion

sommaire chapitre précédent

version imprimable

6. Récursion

6.1. Définition

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 :

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.

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.

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-dessous.

Dans le schéma qui suit, 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.

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

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 récursive : étude des actions

Formalisation :

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 :

Moteur d'automate

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

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

6.4.5. Détail des actions

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

action débuter

action imprimer

action appeler

action terminer

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

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.

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...

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 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).

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

Allocation des "stack frames" propres à chaque procédure,

(chaque stack frame contient entre autres, les variables locales à la procédure correspondante)

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)

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

Allocation des "stack frames" propres à chaque procédure,

(chaque stack frame contient entre autres, les variables locales à la procédure correspondante)

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.

version imprimable

retour vers le haut chapitre suivant