Itération while

La structure d'itération while, moins structurée que for, est plutôt adaptée à l'itération d'une transformation, tant qu'une certaine condition est vérifiée. C'est cette condition qui est spécifiée dans l'en-tête du while, tandis que le corps, qui est un bloc, décrit cette transformation.

Un des plus anciens algorithmes connus, dû à Euclide, permet de calculer le plus grand commun diviseur de deux entiers $a$ et $b$, par itération. L'algorithme utilise deux variables x et y, initialisées aux valeurs $a$ et $b$, puis opère itérativement sur ces variables. L'idée de la transformation est de maintenir l'invariant $\mathop{\normalfont\mathrm{pgcd}}\nolimits (x,y)$ et de s'arrêter quand $x=y$ auquel cas, $\mathop{\normalfont\mathrm{pgcd}}\nolimits (x,y) = x = y$. Euclide savait que si $x>y$, $\mathop{\normalfont\mathrm{pgcd}}\nolimits (x,y) = \mathop{\normalfont\mathrm{pgcd}}\nolimits (x-y,y)$ et que si $y>x$, $\mathop{\normalfont\mathrm{pgcd}}\nolimits (x,y) = \mathop{\normalfont\mathrm{pgcd}}\nolimits (x, y-x)$. D'où l'itération suivante, qu'on peut décrire ainsi en français : << tant que $x$ et $y$ sont différents, soustraire le plus petit du plus grand >> :

  while (x != y) {
    if (x > y) {
      x = x-y;
    } else {
      y = y-x;
    }
  }

Contrairement au for de l'exemple précédent, il n'est pas évident que cette boucle termine⁸, c'est-à-dire qu'il n'y ait qu'un nombre fini d'itérations. En effet si $a$ ou $b$ est $\le 0$, la boucle ne termine pas. Supposons que $a>0$ et $b>0$ ; après initialisation, on a donc $x>0$ et $y>0$; à chaque itération, si $x\not= y$, $\max(a,b)$ décroît strictement, mais reste strictement positif. Il y a donc au plus $\max(a,b)-1$ itérations avant que la condition ne devienne fausse, c'est-à-dire que $x=y$. Ce n'est pas très efficace.

Tout en conservant le même invariant $\mathop{\normalfont\mathrm{pgcd}}\nolimits (x,y)$, on peut choisir d'autres transformations de x et y de sorte que la boucle termine en moins d'itérations ; c'est l'algorithme d'Euclide, dans sa version moderne, où l'on remplace la soustraction par le calcul du reste par division entière (opérateur %), en utilisant l'identité $\mathop{\normalfont\mathrm{pgcd}}\nolimits (x,y) = \mathop{\normalfont\mathrm{pgcd}}\nolimits (x \mathop{\normalfont\mathrm{mod}}\nolimits y,y)$ ; voici ce que donne directement ce remplacement :

  while (x != y) {
    if (x > y) {
      x = x%y;
    } else {
      y = y%x;
    }
  }

Comme $x \mathop{\normalfont\mathrm{mod}}\nolimits y < y$, les tests peuvent être éliminés en faisant en sorte que la valeur de x soit supérieure à celle de y.

int pgcd(int x, int y) {
  while (y > 0) {
     int t = x%y;

     x = y;
     y = t;
  }
  return x;
}

Rappelons que les arguments étant passés par valeur, les affectations aux paramètres x et y ne modifient que des variables locales et en aucune façon les arguments eux-mêmes.

Il existe également une itération do ... while (...);, plus rarement utilisée, qui exécute au moins une fois son corps et s'arrête quand la condition n'est plus vérifiée (on veillera à ne pas oublier le << ; >> final).