Introduction

On peut définir des fonctions récursives, on peut aussi définir des structures de données récursives ! Le premier tel exemple est la liste. Nous verrons ensuite les arbres.

La liste est l’équivalent récursif des tableaux. Une liste peut être vide. Ou bien être constituée d’un élément (la tête) et d’une liste des éléments suivants (la queue).

On peut imaginer une liste comme un serpent : si on lui coupe la tête, il reste la queue. Et la queue est elle-même un serpent.

Représentation graphique sur le blog de Philip Wadler

Contraintes

Nous allons définir une classe (récursive) Liste de la façon suivante:

class Liste {
    public int tete;
    public Liste queue;

    static final Liste VIDE = null;

    public Liste(int tete, Liste queue) {
        this.tete = tete;
        this.queue = queue;
    }

    public static Liste cons(int tete, Liste queue) {
        return new Liste(tete, queue);
    }

    public String toString() {// suppose la liste non vide !
        if (queue == null) {
            return tete + "::[]";
        } else {
            return tete + "::" + queue.toString();
        }
    }
}

Les seules choses que nous aurons le droit de faire sont :

// Créer une liste vide
Liste l = Liste.VIDE;

// Construire une liste à partir
// d'une tête (un élément)
// et d'une queue (une liste)
int tete = 17;
Liste queue = Liste.VIDE;
Liste nouvelle = Liste.cons(tete, queue);
Liste l = Liste.cons(16, nouvelle);

// Accéder au premier élément (tête)
System.out.println(l.tete);

// Accéder à la queue de la liste (liste privée de son premier élément)
System.out.println(l.queue);

// Tester si la liste est vide
if (l == null) { //ou l == Liste.VIDE
    System.out.println("Liste vide");
} else {
    System.out.println("Liste pas vide");
}

Exercices

Dans une autre classe (Main), écrire et tester les fonctions suivantes :

1. taille ou longueur d’une liste

   static int longueur(Liste l) {
       if (l == null) {
           return 0;
       } else {
           return 1 + longueur(l.queue);
       }
   }

2. estDans teste si un élément donné appartient à la liste.

3. concatene met deux listes bout à bout.

4. renverse renvoie la liste à l’envers.

5. Calculer la complexité des fonctions concatene et renverse.

6. maximum renvoie le plus grand élément d’une liste d’entiers.

7. minimum renvoie le plus grand élément d’une liste d’entiers.

8. repete(n, m) renvoie la liste composée de n fois l’élément m.

   > repete(5, 47)
   47::47::47::47::47::[]

9. cycle(n, l) renvoie la liste composée de n fois la liste l.

10. pairs(n) renvoie la liste des n premiers nombres pairs.

11. take(n, l) renvoie la liste des n premiers éléments de l.

12. drop(n, l) renvoie la liste des éléments de l privée des n premiers.

13. last renvoie le dernier élément d’une liste.

14. init renvoie la liste privée de son dernier élément.