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 manipuler des tables lua (équivalent des tableaux) de façon récursive. Les fonctions de base suivantes permettront de manipuler les listes :

function cons(element, liste)
	return {tete = element, queue = liste}
end

function tete(liste)
	return liste.tete
end

function queue(liste)
	return liste.queue
end

function detruit(liste)
	return liste.tete, liste.queue
end

function string(liste)
	if liste == nil then
		return "[]"
	else
		return "[ " .. liste.tete .. " " .. string(liste.queue) .. "]"
	end
end

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

-- Créer une liste vide
l = nil

-- Construire une liste à partir
-- d'une tête (un élément)
-- et d'une queue (une liste)
t = 17
q = nil
nouvelle = cons(t, q)
l = cons(16, nouvelle)

-- Accéder au premier élément (tête)
print(tete(l))

-- Accéder à la queue de la liste (liste privée de son premier élément)
print(string(queue(l)))

-- Couper une liste en sa tête et sa queue
t, q = detruit(l)

-- Tester si la liste est vide
if l == nil then
	print("Liste vide")
else
	print("Liste pas vide")
end

Exercices

taille ou longueur d’une liste

function longueur(l)
	if l == nil then
		return 0
	else
		return 1 + longueur(queue(l))
	end
end

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

concatene met deux listes bout à bout.

> string(concatene(l, l))
[ 1 [ 16 [ 17 [ 1 [ 16 [ 17  []]]]]]]

renverse renvoie la liste à l’envers.
Calculer la complexité des fonctions concatene et renverse.
maximum renvoie le plus grand élément d’une liste d’entiers.
minimum renvoie le plus grand élément d’une liste d’entiers.
repete(n, m) renvoie la liste composée de n fois l’élément m.
```
> string(repete(5, "ah"))
[ ah [ ah [ ah [ ah [ ah []]]]]]
```

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

> ab = cons("a", cons("b", nil))
> string(ab)
[ a [ b []]]
> string(cycle(4, ab))
[ a [ b [ a [ b [ a [ b [ a [ b []]]]]]]]]

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

> lp = doubles(10)
> string(lp)
[ 2 [ 4 [ 6 [ 8 [ 10 [ 12 [ 14 [ 16 [ 18 [ 20 []]]]]]]]]]]

take(n, l) renvoie la liste des n premiers éléments de l.
```
> string(take(4, lp))
[ 2 [ 4 [ 6 [ 8 []]]]]
```
drop(n, l) renvoie la liste des éléments de l privée des n premiers.
```
> string(drop(5, lp))
[ 12 [ 14 [ 16 [ 18 [ 20 []]]]]]
```
last renvoie le dernier élément d’une liste.
```
> last(lp)
20
```

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

> string(init(lp))
[ 2 [ 4 [ 6 [ 8 [ 10 [ 12 [ 14 [ 16 [ 18 []]]]]]]]]]