Récursivité dans l'algorithmique et la programmation/Algorithmes récursifs

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

On peut distinguer plusieurs catégories d'algorithmes récursifs en considérant

• Le mode d'appel : direct/indirect
• Le nombre de paramètres sur lesquels porte la récursion : arité
• Le nombre d'appels récursifs : ordre de récursion
• Le genre de retour : terminal/non terminal

Mode d'appel

Comme nous l'avons déjà vu dans l'introduction, un algorithme récursif qui dans son corps s’appelle lui-même est dit direct. L'exemple de la factorielle est trivial. Un algorithme récursif est dit indirect s'il est défini par un ensemble de fonctions qui s'appellent en chaîne.

Début de l'exemple

Algorithme récursif indirect pour déterminer la parité d'un entier

Pour construire une définition récursive de la parité, remarquons tout d’abord que 0 est un entier pair, et qu’il n’est pas impair. Ensuite remarquons qu'un entier n est pair (respectivement impair) ssi l'entier n-1 est impair (respectivement pair).

Si l’on trace Pair(3) on obtiendra :

${\begin{matrix}Pair(3)&\leftarrow &\operatorname {\underline {Faux}} \\&\searrow &\uparrow \\&&Impair(2)&\leftarrow &\operatorname {\underline {Faux}} \\&&&\searrow &\uparrow \\&&&&Pair(1)&\leftarrow &\operatorname {\underline {Faux}} \\&&&&&\searrow &\uparrow \\&&&&&&Impair(0)\end{matrix}}$

Fin de l'exemple

Arité

L'arité d'un algorithme est le nombre de paramètres d'entrée. Un algorithme récursif peut effectuer des appels récursifs en modifiant un nombre quelconque non nul de ses paramètres. Dans l'exemple de la fonction factorielle, l'algorithme prend un paramètre d'entrée et le modifie lors des appels récursifs. Dans le cas de la puissance entière (proposé en exercice), l'algorithme prend deux entrées, la base et l'exposant. Dans les appels récursifs seul l'exposant est modifié. Voici un exemple de récursion sur deux paramètres.

Début de l'exemple

Algorithme récursif de calcul du PGCD de deux entiers

Fin de l'exemple

Ordre de récursion

Jusqu'à présent, tous les algorithmes récursifs évoqués ne font qu'un appel récursif à la fois, c'est-à-dire que pour déterminer la valeur d'un appel, on n'a besoin que d'un appel récursif. Ces algorithmes sont dits d'ordre 1. Certains algorithmes font plusieurs appels récursifs, comme la version naïve du calcul de la suite de Fibonnaci. Celle-ci doit faire deux appels récursifs, une fois avec le paramètre n-1 et une seconde fois avec le paramètre n-2 pour calculer une valeur de retour. C’est un algorithme récursif d'ordre 2.

Début de l'exemple

Algorithme récursif pour calculer le n^ième terme de la suite de Fibbonacci

Fin de l'exemple

Récursion terminale

Pour déterminer si un algorithme est terminal, il faut regarder comment il génère les valeurs de retour. Si ce sont soit des constantes, soit des valeurs directement issue d'un appel récursif, sans aucune autre modification, alors l'algorithme est dit terminal. Dans le cas contraire, il sera dit non-terminal. Cette notion est importante si l’on veut déterminer une version itérative de l'algorithme concerné. Dans les exemples précédents, factorielle est non terminal car, bien que le cas d'arrêt renvoie une constante, celui de l'appel récursif quant à lui modifie la valeur renvoyée en la multipliant par n avant de lui-même renvoyer une valeur.