Définition

Une procédure ou fonction est dite récursive si elle est définie par elle-même.

Dans les définitions récursives on définit toujours un cas simple (appelé cas trivial) et un cas général. Il faut aussi s'assurer que du cas général et à partir de simplifications successives on arrive au cas trivial. Si on n'a pas cette dernière condition, la définition serait invalide.

Propriétés

Un algorithme récursif ne doit pas générer une séquence infinie d'appels à lui-même. Il doit toujours y avoir une façon de sortir des appels récursifs ("Way out").

Conception d'algorithmes récursifs

Pour certains problèmes, il est beaucoup plus facile de rechercher une solution récursive plutôt qu'une itérative. Le problème des tours de Hanoi constitue un très bon exemple.

Sémantique de la récursion

La récursivité est un outil puissant pour la résolution des problèmes. A chaque appel , la procédure récursive est appelée avec des arguments différents. Tout se passe comme si on a plusieurs copies du code de la procédure. Ainsi pour chaque exécution, les variables locales ainsi que les paramètres en entrée sont réalloués. A un moment donné, seules les dernières allocations sont référencées. Quand un retour est fait, les plus récentes allocations sont libérées et une copie de la procédure est réactivée. C'est donc le mécanisme de pile.

Passage d'algorithmes récursifs en algorithmes itératifs

Plusieurs langages n'acceptent pas la récursivité (Fortran, Cobol, ...). Il est donc quelques fois nécessaire de faire le passage des algorithmes récursifs en algorithmes non récursifs.

Quelques notions de compilation doivent être connues pour comprendre la technique de récursion et donc le passage des algorithmes récursifs en algorithmes itératifs.

A chaque procédure est associée une zone de données qui contient les variables locales, les paramètres, les variables temporaires.

Les zones de données sont gérées en pile.

Au moment d'un appel, il y a sauvegarde de la zone de données de l'appelant, transmission des paramètres ( par valeur ou par référence) et branchement vers le début de la procédure appelée. L'adresse de retour au niveau de l'appelant doit être également sauvegardée dans la zone de données de la procédure appelée.

Au moment d'un retour, il y a restauration de la zone de donnée et continuation de l’exécution de la procédure à partir de l'adresse de retour préalablement sauvegardée dans la zone de donnée de la procédure appelée.

Quand un paramètre est appelé par valeur, la procédure appelée crée une copie de ce paramètre dans sa zone de données. La procédure appelante ignore donc les changement effectués sur ce paramètre par la procédure appelée.

Quand un paramètre est appelé par référence, la procédure transmet l'adresse de ce paramètre. La procédure appelée travaille ainsi directement sur le paramètre de l'appelant par le phénomène de l’indirection.

Technique de passage

Dans un premier temps, on se place dans le contexte suivant : un algorithme fait appel à une fonction récursive. Donc tous les paramètres sont appelés par valeur.

La technique de passage est la suivante :

a) définir la zone de données. Elle contient toutes les variables locales et les paramètres.

b) définir les points d'appel et de retour. Il y a donc toujours un appel dans l'algorithme appelant. C'est le premier appel.

c) au moment de l'appel on fait les opérations suivantes:

- empiler (sauvegarder) la zone de données courante.

- préparer le nouvel appel en préparant la nouvelle zone de données avec les paramètres ( passage de paramètres) et avec l'adresse de retour(point d'appel).

- se brancher vers le début de la fonction.

d) au moment du retour, on fait les opérations suivantes:

- récupérer l'adresse de retour qui se trouve dans la zone de données courante.

- dépiler une zone de données ( restaurer la dernière sauvegardée)

- se brancher vers cette adresse.

e) afin d’éviter un "Underflow", on initialise la pile avec une zone de données "bidon".

Certaines améliorations sont utiles une fois la traduction automatique faite. Comme amélioration, on peut par exemple éliminer toutes les variables dans la pile qui ne servent à rien. Il est aussi souhaitable de transformer l'algorithme afin d'éliminer les "Allera" et d'obtenir un algorithme structuré.

Autres règles pour la transformation

D'autres règles sont nécessaires pour la dérécursification des algorithmes :

a) appel en fin de procédure : on peut toujours éliminer tout appel récursif qui apparaît en fin de procédure. Ca revient à empiler une zone de données et tout de suite après la dépiler. Il est donc inutile de l'empiler. Il suffit de faire :

- changer les valeurs de la zone de données par les nouveaux paramètres.

- se brancher au début de la procédure.

b) utilisation des variables globales.

c) éviter les tableaux comme paramètre.

d) cas de l'appel par valeur et par référence dans une procédure : il ne faut mettre dans la zone de données que les paramètres appelés par valeur. Les paramètres appelés par référence seront considérés comme des variables globales.

Inconvénient

En général, la version non récursive s’exécute plus efficacement en temps et en espace. La raison principale est la pile.

Avantage

Quelquefois, la solution récursive est plus naturelle et plus logique pour résoudre un problème.