UP | HOME

Complément - Récursion et itération

Il est souvent plus simple d'utiliser la récursion pour réaliser une itération que de s'en abstenir. Cependant, en Java, dès que les structures de données dépassent une certaine taille (typiquement de l'ordre de la dizaine de milliers d'éléments), il est nécessaire de s'en abstenir, car Java n'optimise pas la récursion terminale.

Cf. Wikipedia pour la définition de la récursion terminale ("tail recursion" en anglais).

Exemple : implémentation d'ensembles. Cf. le paquet ensembles.

Point de départ : une interface associée à une définition inductive, complète

L'interface peut se construire d'une manière systématique à partir de la définition inductive. Il suffit d'y ajouter tous les sélecteurs, projecteurs et constructeurs (méthodes de fabrication) induits par la définition inductive du type.

Ensemble ::= Vide | Cons(Element, Ensemble) | Union(Ensemble, Ensemble)

Interface Ensemble :

Si l'interface est incomplète, il devient nécessaire de recourir à des tests sur les types pour discriminer (en utilisant l'opérateur instanceof) ou d'exposer les attributs, ce qui ne contribue ni à la lisibilité du code ni à sa maintenabilité.

Une classe d'implémentation par cas dans la définition inductive

Exemple : le cas de l'union

Lorsqu'on construit de manière répétée une union avec une branche gauche très longue, il devient impossible d'itérer : lors de l'exécution, la taille maximale de la pile est atteinte, car la machine virtuelle de Java empile tous les appels, y compris lorsque la récursion est terminale, où elle pourrait simplement remplacer le précédent appel par le nouveau.

Il est nécessaire de réaliser l'itération d'une manière non récursive.

Cf. l'unité de compilation EnsemblesIterables. On peut implémenter l'itérateur sans recours à la récursion en utilisant une boucle.

class Union implements Ensemble {
  private Ensemble gauche;
  private Ensemble droit;
  private int taille;
  // Nouveaux attributs utilisés pour mémoriser la décomposition
  //   (à réifier et externaliser en utilisant le patron Itérateur) 
  private int element;
  private Ensemble reste;
  ...
  // Décomposition avec mémorisation pour éviter de refaire ce long calcul
  private void decomposer(){
    // Precondition : !this.estVide()
    Ensemble courant = this; // Invariant : !courant.estVide()
    while(true){
      // A chaque itération, 
      // - on préserve la valeur ensembliste de courant, et
      // - ou bien on réduit l'expression décrivant l'ensemble,
      // - ou bien on réduit l'expression gauche, après réorganisation
      //   de l'expression.
      if(courant.casCons()){ 
        // Cons(e, r) décomposé en (e, r)
        this.reste = courant.reste();
        this.element = courant.element();
        return;
      }else{ // Union(g, d)
        if(courant.gauche().estVide()){ 
          courant = courant.droit(); 
          // g vide : passage à d
        }else if(courant.gauche().casCons()){ 
          // Union (Cons(e, r), d) décomposé en (e, Union(r, d))
          this.reste = courant.gauche().reste().union(courant.droit());
          this.element = courant.gauche().element();
          return;
        }else{
          // passage de Union(Union(g, d'), d) à Union(g, Union(d', d)) 
          courant = courant.gauche().gauche().union(
                       courant.gauche().droit().union(courant.droit()));
        }
      }
    }
  }
  public int element() {
    if(this.estVide()){
      throw new UnsupportedOperationException();
    }
    if(this.reste != null){
      return this.element;
    }
    decomposer(); 
    return this.element;
  }
  public Ensemble reste() {
    if(this.estVide()){
      throw new UnsupportedOperationException();
    }
    if(this.reste != null){
      return this.reste;
    }
    decomposer();
    return this.reste;
  }

On peut conclure en incluant dans l'interface une méthode retournant un itérateur. Cf. l'unité de compilation EnsemblesIterablesAvecIterateur.

Remarque : dans un langage fonctionnel, l'interface d'un type inductif est complète par construction. Les sélecteurs et les projecteurs sont inclus dans le mécanisme de filtrage ("pattern matching") alors que les constructeurs sont inclus dans la définition du type de données. La récursion terminale est généralement optimisée. La question peut alors se ramener à celle de l'élimination de la récursion non terminale, qui doit être transformée en récursion terminale. Il existe des méthodes générales pour cette transformation, fondées sur des continuations : le principe est d'empiler successivement les traitements à réaliser au retour de chaque appel récursif puis de réduire la pile en dépilant chaque traitement pour l'appliquer.

Cf. fonctions.EliminationRecursion pour un exemple.

Author: Hervé Grall
Version history: v1: 2015-11-02; v2: 2016-10-24[update] ; v3: 2017-10-17[*text]; v4: 2018-11-14[*text].
Comments or questions: Send a mail.
The webpage content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.