Les fonctions récursives en JavaScript

Hanging bears.
Dennis Jarvis

To iterate is human, to recurse divine.

L. Peter Deutsch

La récursivité est un grand concept de la programmation : il s’agit d’une méthode permettant d’obtenir une solution à un problème en utilisant des instances plus petites de ce même problème. En clair, une fonction est donc dite récursive si elle s’appelle elle-même.

La récursivité est une approche de la programmation un peu complexe au premier abord, puisqu’elle s’oppose à la programmation itérative. Mais elle propose des avantages indéniables : sa grande force est de pouvoir résoudre un problème en le divisant en une collection de sous-problèmes, chacun d’entre eux étant résolu par une solution évidente.

Pour bien appréhender ce concept, le sous chapitre suivant est proposé en guise de rappel. Il vous permettra de faire un parallèle avec l’écriture récursive, que je vous explique dans un second temps.

Une boucle, des itérations

Une boucle est une séquence d’instructions qui se répétera jusqu’à ce qu’une certaine condition soit remplie. Cette condition permettant de sortir de la boucle peut être définie à l’aide d’un compteur. On peut ainsi définir une boucle comme étant un bloc de code qui sera exécuté au moins une fois. Et chacune de ces exécutions est appelée une itération.

Les boucles sont plutôt simples à écrire, faciles à comprendre, et elles permettent de gagner un temps non négligeable, qui en plus évite la répétition de code pour chacune des itérations.

En guise d’illustration, je vous propose l’implémentation de la notion mathématique suivante : la factorielle. La factorielle d’un nombre est le produit de tous les entiers de 1 à ce nombre. Ainsi, la factorielle du nombre 5 est égale au produit de 1 x 2 x 3 x 4 x 5. Elle est donc égale à 120. Je crée donc ici une fonction factorial qui va, au moyen de la boucle for, proposer le résultat de factorielle x de manière itérative.

function factorial(x) {
  var result = 1;
  for (var i = 1; i <= x; i++)
    result = result * i;
  return result;
}

factorial(5); // output : 120

Comme vous pouvez le voir, on utilise ici un compteur qui va s'incrémenter en répétant l'action de produire la multiplication entre le résultat précédemment obtenu et ce même compteur. A chaque itération de la boucle, ce compteur change donc de valeur.

Cas de base, cas de propagation

Afin que la récursivité soit effective, deux fonctionnalités clés doivent nécessairement être implémentées. Il s'agit du cas de base et du cas de propagation, aussi parfois appelé simplement le cas récursif.

Le cas de base représente l'ensemble des lignes de code qui permet l'arrêt de la récursion. Habituellement, cet ensemble débute avec une clause conditionnelle comme if. Si cette notion n'est pas mise en place, la fonction sera répétée de manière infinie et le programme plantera. Le case de base est donc la condition de fin de la fonction récursive.

Le cas de propagation représente l'ensemble des lignes de code où aura lieu la récursivité. Il s'agit, en clair, du bloc de code où la fonction fera à nouveau appel à elle-même.

Écrivons de nouveau la fonction factorial mais cette fois de manière récursive.

function factorial(x) {
  // This is the base case.
  if (x === 0) return 1;
  // This is the recursive one.
  else return x * factorial(x - 1);
}

factorial(5); // output : 120

Notre cas de base déclare que si x est égal à 0, nous retournons la valeur 1. Cette fonction factorial va donc s'arrêter au moment où x atteindra la valeur 0. Pour toute autre valeur positive de x, nous retournons, le produit de x et de factorielle x.

Décomposons factorial(5) pas à pas, pour bien comprendre le mécanisme de la récursivité.

factorial(5) = 5 * factorial(4);
factorial(4) = 4 * factorial(3);
factorial(3) = 3 * factorial(2);
factorial(2) = 2 * factorial(1);
factorial(1) = 1 * factorial(0);
factorial(0) = 1;
// Donc :
// factorial(1) = 1 * 1;
// factorial(2) = 2 * 1 * 1;
// factorial(3) = 3 * 2 * 1 * 1;
// factorial(4) = 4 * 3 * 2 * 1 * 1;
// factorial(5) = 5 * 4 * 3 * 2 * 1 * 1 = 120

Penser récursif

Mettre en place des fonctions qui utilisent le principe de la récursivité n'est absolument pas inné. Cependant, il vous permettra d'obtenir des fonctions plus élégantes découpées en de plus petites instances d'elles-même. Mais il faut nécessairement de la pratique !

Ma principale recommandation est de penser en premier lieu au cas de base. C'est grâce à cette condition de fin essentielle que votre programme ne plantera pas et ne tournera pas de manière infinie. Prenez une feuille, posez cette condition et essayez systématiquement de réduire votre problème à une solution simple. Vous pouvez continuer cette réflexion autour de cet article de Santosh Rajan par exemple.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *