|
Dans un sens purement mathématique, une récursion
correspond à n'importe quel processus qui s'appelle lui-même
plus d'une fois en suivant, à chaque occurence, le même
schéma. En programmation, ceci correspond à une fonction
qui s'appelle elle-même.
Compréhension
Il s'agit là d'un concept qui, malgré sa banalité,
reste non trivial à saisir (d'où la célèbre
phrase "Pour comprendre la récursivité, il faut
tout d'abord comprendre la récursivité"... qui
ne peut être comprise que par ceux ayant compris la récursivité!).
Pour ceux d'entre vous qui éprouveraient des difficultés,
voici deux petites "méthodes" pour s'y retrouver:
- le paquet de chips sur lequel on voit une personne tenant un paquet
de chips, sur lequel on voit une personne tenant un paquet de chips,
sur lequel on voit une personne tenant...
- l'histoire d'un petit garçon qui ne voulait pas dormir
et dont la mère lui raconte l'histoire de la petite grenouille
qui ne voulait pas dormir et dont la mère lui raconte l'histoire
de l'ourson ne voulait pas dormir et dont la mère lui raconte
l'histoire du bébé écureuil qui s'est endormi,
et l'ourson s'endormi, et la petite grenouille s'endormi, et le
petit garçon s'endormi.
La première image n'est pas totalement appropriée,
car toute récursivité se doit d'avoir une fin (sans
quoi nous avons droit à une boucle infinie, et le programme
plante...) - mais elle aide à visualiser la chose. Pareillement,
les fonctions fractales sont des fonctions récursives théoriquement
infinies...
La seconde image, en revanche, permet de mieux voir ce qui se produit
lors de la récursivité: on passe au "niveau"
suivant tant qu'on n'a pas atteint la condition d'arrêt (ici,
l'endormissement). Celle-ci atteinte, la récursion se termine
pour les autres niveaux en sens inverse.
Exemple simple
L'exemple le plus simple (et le cas d'école le plus courant)
de la récusivité est le problème de la factorielle
d'un entier. Par exemple, la factorielle de 4:
4! = 1 * 2 * 3 * 4 = 24
Sachant que 3! = 1 * 2 * 3 et que
2! = 1 * 2, nous en tirons rapidement
les progressions suivantes:
4! = 3! * 4
3! = 2! * 3
2! = 1! * 2
1! = 1
2! = 1* 2 = 2
3! = 2 * 3 = 6
4! = 6 * 4 = 24
Une factorielle peut ainsi être appelée par une factorielle.
A chaque appel, la factorielle en cours se met "en attente"
de la résolution de la factorielle suivante. Voici une application
en JavaScript (nous utiliserons ce langage car tous nos lecteurs
ont accès à un compilateur JS: leur navigateur):
<html>
<head>
<script>
function fact(x)
{
if (x <= 1)
return
1;
else
return
x * fact(x - 1);
}
</script>
</head>
<body onLoad="javascript:alert('Résultat='+fact(4));">
</body>
</html>
Restranscrit,
on obtient fact(4) = fact(3) * 4 = ...
. La condition d'arrêt, nécessaire à toute récursion,
est ici de tester si l'entier est égal à 1.
Vous devriez
maintenant avoir une bonne compréhension de la manière
dont la récursivité fonctionne. Voyons maintenant
à quoi elle peut nous servir.
Page 1 | 2
|
[