Algorithmique et programmation/Récursivité/Algorithmes récursifs
Une page de Wikiversité.
 |
|||
| Chapitre 2 | |||
| Leçon : Récursivité | |||
|---|---|---|---|
| Chap. préc. : | Introduction | ||
| Chap. suiv. : | Structure de données récursives | ||
En raison de limitations techniques, la typographie souhaitable du titre, « Algorithmique et programmation/Récursivité : Algorithmes récursifs
Algorithmique et programmation/Récursivité/Algorithmes récursifs », n'a pu être restituée correctement ci-dessus.
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
Sommaire |
[modifier] 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.
|
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 que un entier n est pair (resp. impair) ssi l'entier n-1 est impair (resp. pair).
Si l'on trace Pair(3) on obtiendra
|
[modifier] 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.
|
Algorithme récursif de calcul du PGCD de deux entiers |
|
|
[modifier] 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.
|
Algorithme récursif pour calculer le nième terme de la suite de Fibbonacci |
|
|
[modifier] 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.
