Récursivité
Mise à jour : novembre 2007
La récursivité est une importante technique de programmation qui permet à une fonction de s'appeler elle-même. Le calcul de factorielles constitue un exemple de récurrence. La factorielle de 0 est définie comme égale à 1. La factorielle de n, un entier supérieur à 0, est le produit de tous les entiers de la suite 1 à n.
Utilisation de la récursivité
Le paragraphe suivant correspond à une fonction, définie par des mots, qui calcule une factorielle.
« Si le nombre est inférieur à zéro, le rejeter. Si ce n'est pas un entier, le rejeter. S'il est égal à zéro, sa factorielle sera égale à un. S'il est supérieur à zéro, le multiplier par la factorielle du nombre immédiatement inférieur. »
Pour calculer la factorielle d'un nombre supérieur à zéro, vous devez calculer la factorielle d'au moins un autre nombre. La fonction doit s'appeler sur le nombre directement inférieur avant de pouvoir s'exécuter sur le nombre actuel. C'est un exemple de récursivité.
La récursivité et l'itération (exécution d'une boucle) sont fortement liées : une fonction peut retourner les mêmes résultats avec la récursivité ou avec l'itération. Généralement, un calcul particulier utilisera l'une ou l'autre technique, mais rien ne vous empêche de choisir l'approche qui vous semble la plus naturelle ou la plus appropriée.
Si la récursivité est utile, il faut toutefois être prudent lors de son utilisation, car il est facile de créer une fonction récursive qui ne retourne jamais de résultat et ne peut atteindre un point de terminaison. Une telle récursivité provoque l'exécution d'une boucle sans fin. En voici un exemple : ignorez la première règle (celle qui est relative aux nombres négatifs) de la description verbale du calcul d'une factorielle et essayez de calculer la factorielle d'un nombre négatif. La procédure échoue car pour calculer la factorielle, par exemple, de -24, vous devez calculer la factorielle de -25. Pour pouvoir calculer la factorielle de -25, vous devez calculer auparavant la factorielle de -26, etc. Ce calcul est, par conséquent, sans fin.
Un autre problème lié à la récursivité est qu'une fonction peut utiliser toutes les ressources disponibles (telles que la mémoire système et l'espace de pile). Chaque fois qu'une fonction récursive s'appelle (ou appelle une autre fonction qui appelle la fonction d'origine), elle utilise certaines ressources. Ces ressources sont libérées lorsque la fonction récursive se termine, mais une fonction qui possède un nombre trop important de niveaux de récursivité est susceptible d'utiliser toutes les ressources disponibles. Une telle situation lève une exception.
C'est pourquoi il est important d'être très prudent lors de la conception de fonctions récursives. Si vous pensez pouvoir être confronté à une récursivité excessive ou infinie, créez la fonction de telle sorte qu'elle compte le nombre d'appels à elle-même et définissez une limite pour le nombre d'appels. Si le seuil d'appels de la fonction à elle-même est dépassé, la fonction peut automatiquement se terminer. Le nombre optimal et maximal d'itérations dépend de la fonction récursive.
Reprenons la même fonction factorielle, mais cette fois écrite en code JScript. L'annotation de type est utilisée afin que la fonction n'accepte que les entiers. Si un nombre non valide est passé (un nombre inférieur à zéro), l'instruction throw génère une erreur. Sinon, une fonction récursive est utilisée pour calculer la factorielle. La fonction récursive accepte deux arguments, le premier pour l'argument de la factorielle et l'autre pour le compteur qui assure le suivi du niveau de récursivité actuel. Si le compteur n'atteint pas le niveau de récursivité maximum, la factorielle du nombre d'origine est retournée.
function factorialWork(aNumber : int, recursNumber : int ) : double {
// recursNumber keeps track of the number of iterations so far.
if (aNumber == 0) { // If the number is 0, its factorial is 1.
return 1.;
} else {
if(recursNumber > 100) {
throw("Too many levels of recursion.");
} else { // Otherwise, recurse again.
return (aNumber * factorialWork(aNumber - 1, recursNumber + 1));
}
}
}
function factorial(aNumber : int) : double {
// Use type annotation to only accept numbers coercible to integers.
// double is used for the return type to allow very large numbers to be returned.
if(aNumber < 0) {
throw("Cannot take the factorial of a negative number.");
} else { // Call the recursive function.
return factorialWork(aNumber, 0);
}
}
// Call the factorial function for two values.
print(factorial(5));
print(factorial(80));
Le résultat généré par ce programme est le suivant :
120
7.156945704626378e+118