Version du 16 juin 2021
Focus sur la récursivité¶
Nous allons maintenant programmer l’algorithme du tri par fusion. Pour rappel, dans sa première phase l’algorithme divise le tableau par deux, comme illustré dans la Figure Diviser du tri à fusion :
def tri_fusion(elements):
# phase de division
milieu = len(elements)//2
elements_gauche = elements[:milieu]
elements_droite = elements[milieu:]
Vous pouvez imprimer l’état des variables pour une meilleure visibilité. Notez que l’on utilise une division entière, car les indices pour accéder aux éléments du tableau doivent être des entiers. Par exemple, si le tableau contient 5 éléments, cela n’aurait pas de sens de prendre les premiers 2.5 éléments.
Ce qui suit est très intéressant. Dans l’étape d’après, on procède exactement de la même manière pour les nouveaux tableaux obtenus (elements_gauche et elements_droite) - on les divise à nouveau en deux :
# phase de division
milieu = len(elements)//2
elements_gauche = tri_fusion(elements[:milieu])
elements_droite = tri_fusion(elements[milieu:])
Regardez bien ce qui se passe. Nous avons fait appel à la même fonction tri_fusion que l’on est en train de définir ! Pour l’instant cette fonction ne fait que diviser un tableau en deux, elle va donc diviser chaque partie d’elements à nouveau en deux. La fonction tri_fusion appelle la fonction tri_fusion (donc elle-même), qui appelle aussi tri_fusion et ainsi de suite.
Le problème ici est que l’appel à tri_fusion ne s’arrête jamais. En réalité, il faut arrêter de diviser lorsque les tableaux obtenus ont au moins un élément ou lorsque les tableaux sont vides :
# phase de division (récursive) de l’algorithme de tri
def tri_fusion(elements):
# condition qui arrête la récursion
if len(elements) <= 1:
return elements
# phase de division
milieu = len(elements)//2
elements_gauche = tri_fusion(elements[:milieu])
elements_droite = tri_fusion(elements[milieu:])
return fusion(elements_gauche, elements_droite)
On appelle une fonction qui s’appelle elle-même une [fonction récursive. C’est une sorte de mise en abime ou une définition circulaire. Lorsqu’on entre dans la fonction, des opérations sont exécutées et on fait à nouveau [appel à la même fonction, mais avec d’autres éléments, afin de refaire les mêmes opérations (voir figure ci-dessous).
Fig. 40 Schéma d’une fonction récursive¶
Le deuxième ingrédient indispensable à toute fonction récursive est la condition d’arrêt : à quel moment tous ces appels imbriqués les uns dans les autres doivent-ils s’arrêter ? Sans cette condition, le programme ne s’arrête jamais. Il est important que la condition d’arrêt précède l’appel à la fonction récursive. Pourquoi ?
A la fin du programme, nous avons rajouté une ligne de code qui correspond à la deuxième phase de l’algorithme – à la fusion des deux listes triées (voir la Figure Fusionner du tri fusion). Il faut maintenant définir cette fonction fusion, que nous allons également définir de manière récursive.
# phase de fusion (récursive) de l’algorithme de tri
def fusion(elements_gauche, elements_droite):
# trouve le plus petit premier élément des deux listes
if elements_gauche[0] < elements_droite[0]:
# appelle fusion récursivement avec le reste des listes
liste_reste = fusion(elements_gauche[1:], elements_droite)
liste_fusionnée = [elements_gauche[0]] + liste_reste
else:
# appelle fusion récursivement avec le reste des listes
liste_reste = fusion(elements_gauche, elements_droite[1:])
liste_fusionnee = [elements_droite[0]] + liste_reste
return liste_fusionnee
Quelle est la différence entre le code dans la partie if de la condition et dans la partie else de la condition (relisez le 3e paragraphe de la solution de l’exercice 9) ? Lorsqu’on fusionne deux tableaux triés, on commence par prendre le plus petit des premiers éléments des deux tableaux à fusionner, que l’on met au début de notre tableau fusionné. On refait ensuite la même opération : on sélectionne le plus petit élément des éléments qui restent dans nos tableaux de départ et on le met à la suite de notre tableau fusionné.
Dans la partie if de la fonction fusion, c’est le tableau de gauche qui contient le plus petit élément. On met cet élément au début de notre nouvelle liste fusionnée et on appelle la fonction fusion sur les éléments restants. Dans la partie else on fait la même chose, sauf que l’on commence notre tableau par le premier élément du tableau de droite. Mais qu’est-ce qui manque à cette fonction ?
Oui, vous avez raison, il manque la condition d’arrêt. Comme avant, on peut arrêter la fusion lorsqu’un des deux tableaux à fusionner est vide. Dans ce cas la solution de fusionner un tableau vide avec un autre tableau est triviale : c’est l’autre tableau (non vide).
# phase de fusion (récursive) de l’algorithme de tri
def fusion(elements_gauche, elements_droite):
# conditions d’arrêt de la récursivité
if elements_gauche == []:
return elements_droite
if elements_droite == []:
return elements_gauche
# trouve le plus petit premier élément des deux listes
if elements_gauche[0] < elements_droite[0]:
# appelle fusion récursivement avec le reste des listes
liste_reste = fusion(elements_gauche[1:], elements_droite)
liste_fusionnée = [elements_gauche[0]] + liste_reste
else:
# appelle fusion récursivement avec le reste des listes
liste_reste = fusion(elements_gauche, elements_droite[1:])
liste_fusionnee = [elements_droite[0]] + liste_reste
return liste_fusionnee
Ces deux fonctions implémentent l’algorithme de tri par fusion de manière récursive. La récursivité est un concept difficile à appréhender. Le mieux c’est d’essayer de coder des algorithmes récursifs et d’afficher ce qui se passe au fur et à mesure.
Exercice 13 
La fonction factorielle n! en mathématiques est le produit de tous les nombres entiers jusqu’à n. C’est une des fonctions les plus simples à calculer de manière récursive. Elle peut être définie comme ceci :
n! = (n-1)! * n
Programmer cette fonction de manière récursive en Python. Proposer également une implémentation itérative de la factorielle où les éléments de 1 à n sont traités l’un après l’autre.
Solution de l’exercice 13
Exercice 14
En Python, proposer une fonction qui inverse l’ordre des lettres dans un mot. Vous pouvez parcourir les lettres du mot directement ou à travers un indice.
Proposer une autre fonction qui inverse l’ordre des lettres dans un mot de manière récursive.
Solution de l’exercice 14
Exercice 15
Les fractales sont des objets géométriques, dont la définition récursive est naturelle. Essayer le code suivant pour différentes valeurs de n (augmenter à chaque fois de 1).
Essayez de comprendre comment le flocon se construit, de manière récursive. Vous pouvez aussi varier la longueur du segment dessiné et la vitesse d’affichage en décommentant la ligne correspondante.
Exercice 16
Implémenter l’algorithme du tri rapide de manière récursive, puis comparer sa vitesse à celle de l’algorithme du tri par sélection.
Solution de l’exercice 16