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 listes python (équivalent des tableaux) de façon récursive. Les fonctions de base suivantes permettront de manipuler les listes :
def cons(element, liste):
return [element] + liste
def tete(liste):
return liste[0]
def queue(liste):
return liste[1:]
def detruit(liste):
return liste[0], liste[1:]
Les seules choses que nous aurons le droit de faire sont :
# Créer une liste vide
= []
l
# Construire une liste à partir
# d'une tête (un élément)
# et d'une queue (une liste)
= 17
t = []
q = cons(t, q)
nouvelle = cons(16, nouvelle)
l
# 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(queue(l))
# Couper une liste en sa tête et sa queue
= detruit(l)
t, q
# Tester si la liste est vide
if l == []:
print("Liste vide")
else:
print("Liste pas vide")
Exercices
taille ou longueur d’une liste
def longueur(l): if l == []: return 0 else: return 1 + longueur(queue(l))
estDans
teste si un élément donné appartient à la liste.concatene
met deux listes bout à bout.renverse
renvoie la liste à l’envers.Calculer la complexité des fonctions
concatene
etrenverse
.maximum
renvoie le plus grand élément d’une liste d’entiers.minimum
renvoie le plus grand élément d’une liste d’entiers.repeat(n, m)
renvoie la liste composée den
fois l’élémentm
.>>> repeat(5, "ah") ["ah", "ah", "ah", "ah", "ah"]
cycle(n, l)
renvoie la liste composée den
fois la listel
.>>> cycle(4, ["a","b"]) ["a", "b", "a", "b", "a", "b", "a", "b"]
pairs(n)
renvoie la liste des n premiers nombres pairs.>>> lp = pairs(10) >>> lp [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
take(n, l)
renvoie la liste desn
premiers éléments del
.>>> take(4, lp) [2, 4, 6, 8]
drop(n, l)
renvoie la liste des éléments del
privée desn
premiers.>>> 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.>>> init(lp) [2, 4, 6, 8, 10, 12, 14, 16, 18]