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 ^4.2, 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.

  static 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).