Récursion et pile

Revenons aux fonctions et étudions-les plus en profondeur.

Notre premier sujet sera la recursion.

Si vous n’êtes pas novice en programmation, cela vous est probablement familier et vous pouvez sauter ce chapitre.

La récursion est un modèle de programmation utile dans les situations où une tâche peut être naturellement divisée en plusieurs tâches du même type, mais plus simple. Ou lorsqu’une tâche peut être simplifiée en une action facile plus une variante plus simple de la même tâche. Ou, comme nous le verrons bientôt, pour traiter certaines structures de données.

Lorsqu’une fonction résout une tâche, elle peut appeler de nombreuses autres fonctions. Cela se produit partiellement lorsqu’une fonction s’appelle elle-même. Cela s’appelle la récursion.

Deux façons de penser

Prenons quelque chose de simple pour commencer – écrivons une fonction pow(x, n) qui élève x à une puissance naturel de n. En d’autres termes, multiplie x par lui-même n fois.

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

Il y a deux façons de le mettre en œuvre.

1. La pensée itérative: la boucle for:

   function pow(x, n) {
     let result = 1;
   
     // multiplier le résultat par x n fois dans la boucle
     for (let i = 0; i < n; i++) {
       result *= x;
     }
   
     return result;
   }
   
   alert( pow(2, 3) ); // 8

2. La pensée récursive: simplifie la tâche et s’appele elle-même:

   function pow(x, n) {
     if (n == 1) {
       return x;
     } else {
       return x * pow(x, n - 1);
     }
   }
   
   alert( pow(2, 3) ); // 8

Veuillez noter en quoi la variante récursive est fondamentalement différente.

Quand pow(x, n) est appelé, l’exécution se scinde en deux branches:

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

1. Si n == 1, alors tout est trivial. On l’appelle la base de la récursion, car elle produit immédiatement le résultat évident: pow(x, 1) équivaut à x.
2. Sinon, nous pouvons représenter pow(x, n) comme x * pow(x, n - 1). En maths, on écrirait xn = x * xn-1. Ceci s’appelle une étape récursive: nous transformons la tâche en une action plus simple (multiplication par x) et un appel plus simple de la même tâche (pow avec le petit n). Les prochaines étapes le simplifient de plus en plus jusqu’à ce que n atteigne 1.

On peut aussi dire que pow s’appelle récursivement jusqu’à ce que n == 1.