2.4 Itérations

C'est l'un des piliers du style impératif. Itérer consiste à répéter l'exécution d'une instruction un certain nombre de fois, ce nombre étant contrôlé par l'évaluation d'une condition booléenne. Java offre trois structures de contrôle itératives :

  for (initialisation ; condition ; transformation) instruction
  while (condition) instruction
  do instruction while (condition);

La structure d'itération for (...;...;...) ... est bien adaptée au parcours de certaines structures de données, notamment un intervalle d'entiers, un tableau, une liste, etc. Par exemple, pour calculer la somme des entiers entre 1 et $n$, on écrit :

  static int sommerEntiers(int n) {
    int somme = 0;
    for (int i=1; i<=n; i++) {
      somme = somme + i;
    }
    return somme;
  }

Une boucle for est spécifiée par trois expressions d'en-tête qui sont, dans l'ordre, une initialisation de la variable d'itération (ici, int i=1), une condition d'exécution (i<=n), et une transformation de la variable d'itération (i++). Le corps d'une boucle est un bloc quelconque ; le corps est exécuté un certain nombre de fois, ce nombre étant contrôlé par les expressions d'en-tête ; chaque exécution du corps est appelée une itération de la boucle.

Dans l'exemple ci-dessus, la variable d'itération i est déclarée comme une variable locale à la boucle et initialisée à 1 ; si la valeur de i est $\le n$, le corps de la boucle est exécuté, puis i est incrémentée par i++, instruction équivalente à i = i+1 ; si la valeur i n'est pas $\le n$, la boucle est terminée ; il y a ici $n$ itérations. La nature impérative de cette structure provient de l'utilisation des variables somme et i qui sont affectées d'une nouvelle valeur à chaque itération.

La portée d'une variable déclarée dans l'initialisation d'un for est l'ensemble de la boucle (en-tête et corps).

La structure d'itération while (cond) instruction, 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 l'instruction, , appelée le corps de l'itération, décrit cette transformation. Ce corps est généralement un bloc d'instructions. Il est exécuté tant que la valeur de la condition est true ; en particulier, elle n'est pas exécutée si sa valeur est false. Hormis quelques situations où l'on souhaite que que le bloc soit exécuté indéfiniment, il importe de faire en sorte que la condition devienne false, afin que l'itération s'arrête.

2.4.0.0.1 L'algorithme d'Euclide

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^2.1, 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).

2.4.0.0.2 Récursion contre itération

Il n'y a aucune différence de principe, du point de vue de l'exécution, entre des fonctions définies récursivement ou pas. Le mécanisme d'allocation sur la pile des cadres d'invocation s'applique de façon identique. Cependant, en l'absence de définitions récursives, chaque fonction a au plus un seul cadre d'invocation en cours. Il en résulte que la pile d'exécution est bornée ; elle peut être allouée initialement et ne croît pas en cours d'exécution. Le programme opère par transformations de cette zone mémoire fixe. On dit que le programme est itératif. S'il existe des définitions récursives, la pile d'exécution n'est pas bornée, croissant et décroissant pendant l'exécution. C'est le principal reproche adressé aux programmes utilisant des définitions récursives : ils consomment de l'espace mémoire, et bien qu'automatique, la gestion de la pile prend aussi du temps. Les programmeurs soucieux de l'efficacité de leurs programmes préfèrent donc les programmes itératifs, basés sur des structures d'itération. Ceux qui privilégient la facilité d'écriture et de compréhension des programmes n'hésitent pas à écrire des programmes récursifs.

2.4.0.0.3 Récursivité terminale

Une invocation récursive d'une fonction f est dite terminale si elle est de la forme return f(...); ; autrement dit, la valeur retournée est directement la valeur obtenue par l'invocation récursive, sans qu'il n'y ait d'opération sur cette valeur. Par exemple, l'invocation récursive de la factorielle

    return n*f(n-1);

n'est pas terminale, puisqu'il y a multiplication par n avant de retourner. Par contre, l'invocation récursive dans

  static int f(int n, int a) {
    if (n<=1) {
      return a;
    } else {
      return f(n-1,n*a);
    }
  }

est terminale. Dans cette version, le paramètre a joue le rôle d'un accumulateur ; l'évaluation de f(5,1) conduit à la suite d'invocations

$$\mathtt{f(5,1)} \to \mathtt{f(4,5)} \to \mathtt{f(3,20)} \to \mathtt{f(2,60)} \to \mathtt{f(1,120)} \to$$

dont la suite de retours

$$\mathtt{f(1,120)} \stackrel{120}{\to} \mathtt{f(2,60)} \stac... ...(4,5)} \stackrel{120}{\to} \mathtt{f(5,1)} \stackrel{120}{\to}$$

est en fait une suite d'égalités

$$\mathtt{f(5,1)} = \mathtt{f(4,5)} = \mathtt{f(3,20)} = \mathtt{f(2,60)} = \mathtt{f(1,120)} = \mathtt{120}$$

Une définition de fonction est récursive terminale quand toute invocation récursive est terminale. La plupart des langages fonctionnels, notamment Caml, exécutent un programme à récursivité terminale comme s'il était itératif, c'est-à-dire en espace constant. Certains compilateurs d'autres langages ont partiellement cette capacité. Sinon, il est facile de transformer une définition récursive terminale en itération pour optimiser l'exécution. Le programme dérécursivé est :

  static int factIter(int n) {
    int a = 1;
    while (n>1) {
      a = n*a;
      n = n-1;
    }
    return a;
  }