Boucles

Écrire cent fois la même ligne n'est pas une option. La boucle est la construction qui permet à quinze lignes d'algorithme de traiter un million de données — et c'est précisément ce qui rend une machine utile.

Tant que : répéter jusqu'à ce que la condition tombe

1TantQue condition Faire2    ...instructions...3FinTantQue

Le mécanisme tient en trois temps, et l'ordre compte. On évalue la condition. Si elle est VRAIE, on exécute le corps, puis on revient au test. Si elle est FAUSSE, on saute directement après le FinTantQue.

Conséquence importante : le test a lieu avant le corps. Si la condition est fausse dès le départ, le corps n'est jamais exécuté. Zéro tour est un résultat parfaitement normal, et souvent le comportement correct — une boucle qui traite les éléments d'une liste vide ne doit rien faire.

Compteur et accumulateur

Presque toute boucle utile met en scène deux rôles distincts, qu'il faut apprendre à distinguer.

Le compteur sait où on en est : i ← i + 1 à chaque tour. Il ne dépend pas du contenu traité, seulement du nombre de tours effectués.

L'accumulateur garde la mémoire de ce qui a été traité : somme ← somme + i. Sa valeur finale est le résultat de l'algorithme.

Les deux doivent être initialisés avant la boucle. Et cette initialisation n'est pas arbitraire : un accumulateur de somme part de 0, l'élément neutre de l'addition ; un accumulateur de produit part de 1. Partir de 0 pour un produit donnerait invariablement 0.

Cliquez l'étape 5, puis l'étape 15. Entre les deux, le même bloc de trois lignes a été parcouru quatre fois — c'est exactement ce que « boucle » veut dire. Et remarquez l'étape 15 : i vaut 5 à la sortie, pas 4. Le compteur dépasse toujours d'un cran la dernière valeur traitée, puisque c'est ce dépassement qui fait échouer le test et arrête la boucle.

La boucle infinie

Retirez la ligne i ← i + 1 de la trace précédente. i reste à 1, le test 1 ≤ 4 reste vrai, et la boucle tourne pour toujours. C'est l'erreur la plus courante du semestre, et elle viole la première exigence de la leçon 1 : la finitude.

La règle de relecture est simple : le corps de la boucle doit contenir quelque chose qui fait progresser la condition vers FAUX. Si vous ne trouvez pas cette instruction, la boucle ne s'arrêtera pas.

Pour : quand le nombre de tours est connu d'avance

1Pour i de 1 à 4 Faire2    somme ← somme + i3FinPour

Cette boucle fait exactement la même chose que la trace ci-dessus, en trois lignes au lieu de sept. Le Pour regroupe au même endroit l'initialisation du compteur, le test et l'incrément — ce qui rend l'oubli de l'incrément impossible. C'est sa vraie qualité, bien plus que la concision.

Les bornes sont incluses des deux côtés : Pour i de 1 à 4 fait quatre tours, avec i valant successivement 1, 2, 3 puis 4.

Le choix entre les deux se fait sur une seule question : sait-on compter les tours avant d'entrer dans la boucle ?

Tout Pour peut se réécrire en TantQue ; l'inverse est faux. Un Pour est un TantQue discipliné.

Cette somme des entiers de 1 à $n$ a d'ailleurs une formule fermée, connue depuis l'Antiquité :

Elle donne le même résultat que la boucle, mais en une seule opération au lieu de $n$. Gardez-la en tête : nous la retrouverons à la leçon 8, quand il s'agira de compter le travail d'un algorithme de tri.

À vous

// 1. Corrigez la boucle Tant que pour qu'elle somme les entiers de 1 à n.
// 2. Écrivez ensuite la même chose avec une boucle Pour.
function sommeTantQue(n) {
  let i = 1;
  let somme = 0;
  while (i <= 0) {   // ← condition à corriger
    // à compléter : accumuler, PUIS avancer le compteur
  }
  return somme;
}

function sommePour(n) {
  let somme = 0;
  // à compléter
  return somme;
}

console.log(sommeTantQue(4), sommePour(4));      // attendu : 10 10
console.log(sommeTantQue(100), sommePour(100));  // attendu : 5050 5050

function sommeTantQue(n) {
  let i = 1;
  let somme = 0;
  while (i <= n) {
    somme = somme + i;
    i = i + 1;       // sans cette ligne : boucle infinie
  }
  return somme;
}

// Quand le nombre de tours est connu d'avance, la boucle Pour dit la même
// chose en une ligne : déclaration, condition et avancement au même endroit,
// donc impossible d'oublier l'incrément.
function sommePour(n) {
  let somme = 0;
  for (let i = 1; i <= n; i++) {
    somme = somme + i;
  }
  return somme;
}

console.log(sommeTantQue(4), sommePour(4));
console.log(sommeTantQue(100), sommePour(100));

À retenir