Un exemple : l'exponentiation1#1

Java ne disposant pas d'un opérateur d'exponentiation entière, il faut programmer cette opération (dans le cas des nombres flottants, utiliser Math.exp). Le programme suivant calcule 85#85, pour des entiers 70#70 et 86#86 avec 87#87, en accumulant (par multiplication) 70#70 dans 71#71, ceci 86#86 fois, l'expression 88#88 étant un invariant de boucle :

  static int exp(int x, int e) {
    int y = 1;
    while (e != 0) {
      y = y*x;
      e = e-1;
    }
    return y;
  }

Chaque itération effectue une transformation 89#89 ; par exemple, le calcul de exp(5,8) effectue les transformations successives suivantes de 90#90 :

91#91

On vérifie l'invariant

92#92

On a donc l'égalité de valeur de cet invariant au début de la boucle (quand 93#93) et à la fin de la boucle (quand 94#94) :

95#95

On notera que la version récursive équivalente à ce programme itératif n'est pas celle que l'on écrirait directement à partir de la définition par récurrence de la fonction puissance, mais est la suivante (la boucle du while modifiant les variables y et e, la fonction récursive doit prendre ces valeurs en argument) :

  static int exp_aux(int x, int y, int e) {
    if (e == 0) {
      return y;
    } else {
      return exp_aux(x, y*x, e-1);
    }
  }
  
  static int exp(int x, int e) {
    return exp_aux(x,1,e);
  }

Pour les trois programmes précédents, le nombre d'itérations ou d'appels récursifs est l'entier 86#86. Il est possible d'accélérer significativement ce calcul en ramenant ce nombre de 86#86 à au plus 96#96, grâce à la propriété suivante^2.2 :

97#97

Par exemple, 98#98 en cinq multiplications au lieu de 9. On obtient ainsi la définition

  static int exp_fastrec_aux(int x, int y, int e) {
    if (e == 0) {
      return y;
    } else if (e % 2 == 1) {
      return exp_fastrec_aux(x, x*y, e-1);
    } else {
      return exp_fastrec_aux(x*x, y, e/2);
    }
  }

La version itérative s'écrit facilement à partir de cette version récursive terminale, en remplaçant la liste des arguments des appels récursifs par des affectations appropriées :

  static int exp_fastiter(int x, int e) {
    int y = 1;
    while (e!=0) {
      if (e%2 == 1) {
        y = x*y;
        e = e-1;
      } else {
        x = x*x;
        e = e/2;
      }
    }
    return y;
  }

Le cas bénéficiant de la plus forte accélération est celui où l'exposant est une puissance de 2 ; voici la suite des transformations de 99#99 pour le calcul de 100#100 (en quatre itérations au lieu de huit):

101#101

La situation est moins favorable quand l'exposant n'est pas une puissance de 2 ; le calcul de 102#102 se fait en 5 itérations, soit moins de 103#103 :

104#104