Comprendre le concept de récursivité en programmation

La récursivité est une technique de programmation où une fonction s'appelle elle-même pour résoudre un problème.

Elle permet de diviser un problème complexe en sous-problèmes plus simples, jusqu'à atteindre un “cas de base”, c'est-à-dire une situation où la fonction peut retourner une solution sans s'appeler à nouveau.

On parle également parfois de “condition d’arrêt”

Qu’est-ce que la récursivité ?

En programmation, une fonction récursive comporte deux parties essentielles :

• Le cas de base : C'est la condition qui met fin à la récursion. Sans cas de base, la fonction entrerait dans une boucle infinie.
• L'appel récursif : C'est l'invocation de la fonction à l'intérieur d'elle-même, pour approcher progressivement le cas de base.

Un des exemples classiques de récursivité est le calcul de la factorielle d’un nombre. La factorielle de n (notée n!) est le produit de tous les entiers de 1 à n. Par exemple, 5! = 5 * 4 * 3 * 2 * 1 = 120.

Un exemple d’utilisation

Une fonction récursive peut être utilisée pour énormément de cas qui nécessiteraient une boucle classique, mais on les trouve également très souvent pour résoudre des problèmes mathématiques.

Par exemple pour résoudre la factorielle d’un nombre

En mathématiques, la factorielle d'un nombre entier positif n (notée n!) est le produit de tous les entiers positifs de 1 à n.

Exemple : la factoriel du nombre 5 est noté 5! et est égal à 5×4×3×2×1 = 120

Et voici comment on pourrait résoudre la factorielle d’un nombre avec une boucle récursive (en pseudo-code) :

Fonction Factorielle(n)
    Si n est égal à 0 ou 1
        Retourner 1
    Sinon
        Retourner n * Factorielle(n - 1)
Fin Fonction

Par convention en mathématiques 0!=1, voilà pourquoi la condition d’arrêt est valable pour le cas 0 et 1

Implémentation en JavaScript

Voici comment implémenter la même fonction récursive pour calculer la factorielle d'un nombre, mais cette fois en JavaScript :

function factorial(n) {
  // Cas de base : la factorielle de 0 ou 1 est 1
  if (n === 0 || n === 1) {
    return 1;
  }
  // Appel récursif
  return n * factorial(n - 1);
}

console.log(factorial(5));

Si l’on avait voulu implémenter le même algorithme avec une boucle while, voici ce que ça pourrait donner :

function factorial(n) {
  let result = 1;
  
  while (n > 1) {
    result *= n;
    n--;
  }
  
  return result;
}

Vous noterez que les deux solutions sont assez proches l’une de l’autre, simplement la version avec boucle a besoin d’une variable result intermédiaire en plus.

Pourquoi utiliser la récursivité ?

La récursivité permet principalement de rédiger un code plus épuré et plus “élégant”, mais attention : une solution récursive est souvent plus lente qu’une solution itérative (boucle).

Hormis pour certains langages compilés qui optimisent la résolution du “cas de base”.

Il existe quelques cas d’usage où la récursivité est intéressante en terme de syntaxe comme pour le parcours d’arbres, de listes chaînées, ou lorsqu’un problème peut facilement $etre divisé en sous-problème.

Mais attention à la profondeur de la récursion, car la “pile d’appel”, qui stocke tous les appels de fonction peut se remplir et l’exécution de votre programme s’arrêter complètement, on parle alors de “dépassement de pile” ou “stack overflow”

Si vous souhaitez aller plus loin dans les avantages et les inconvénients de la récursivité, je vous recommande cet article (anglais) : https://medium.com/@williambdale/recursion-the-pros-and-cons-76d32d75973a