Une introduction à la récursivité

Dans ce cours, Frédéric, professeur de numérique et sciences informatiques propose d'étudier la notion de programmation dite récursive. Puis de l'illustrer par de nombreux exemples, en comparaison avec la programmation classique, dite itérative. On voit comment passer de l’une à l’autre quand c’est possible, comment se déroule l’exécution d’un programme récursif, les avantages et les inconvénients de chaque type d’écriture, en terme de simplicité et d’efficacité. L’exposé se termine par un exemple de programmation récursive particulièrement efficace autour du problème de la recherche d’un chemin dans un labyrinthe.

Téléchargez le support de cours en PDF.

Définition et premiers exemples de récursivité

Qu’est-ce qu’un programme récursif ?

Un programme récursif c’est un programme qui s’appelle lui-même.

Un programme non récursif est dit itératif.

La récursivité, pour quoi faire ?

Si un problème donné peut se ramener à un problème plus « petit », et comme cela de proche en proche jusqu’à un problème élémentaire que l’on sait traiter, alors ce problème peut être traité par une programmation récursive.

Pour qu’un programme récursif s’arrête, il doit obligatoirement comporter une terminaison, c’est-à-dire un cas où il ne s’appelle pas lui-même. Et il faut que la « taille » du problème à traiter diminue à chaque étape.

► Exemple : inversion de l’ordre des éléments d’une liste

Inversion de la liste [2,6,4,9]→[9,4,6,2]

• pour inverser une liste de longueur 0 ou 1, il n’y a rien à faire.
• pour inverser une liste de longueur n il suffit de savoir le faire avec une liste de longueur n - 1 : on inverse la liste des n - 1 derniers éléments et on ajoute le premier élément à la fin.

Description de l’exécution de inversion ([9,2,7]) :

La programmation récursive est-elle efficace ?

La programmation récursive est-elle plus efficace que la programmation itérative ?

Les algorithmes récursifs sont souvent plus gourmands en ressources (mémoire) que leurs équivalents itératifs.

Les algorithmes récursifs programmés sans faire attention au nombre d’appels récursifs sont moins efficaces que leurs équivalents itératifs.

► Exemple : tri par fusion

On veut trier une liste de nombres dans l’ordre croissant.
Exemple : tri([5,1,8,3,0,2,7]) → [0,1,2,3,5,7,8]

Forme récursive :

• une liste d’un ou zéro nombre est déjà triée ;
• si la liste est scindée en deux sous-listes déjà triées, il est rapide d’obtenir la liste complète triée par « fusion ».

→ c’est un exemple de la stratégie « diviser pour régner ».

Qu’est-ce que la fusion de listes triées ?

Comment deux sous-listes triées donnent la liste complète triée.
Exemple :
fusion ([1,3,5,8,9],[0,2,7]) → []
fusion ([1,3,5,8,9],[0,2,7]) → [0]
fusion ([1,3,5,8,9],[0,2,7]) → [0,1]
fusion ([1,3,5,8,9],[0,2,7]) → [0,1,2]
fusion ([1,3,5,8,9],[0,2,7]) → [0,1,2,3]
fusion ([1,3,5,8,9],[0,2,7]) → [0,1,2,3,5]
fusion ([1,3,5,8,9],[0,2,7]) → [0,1,2,3,5,7]
L’une des listes a été complètement utilisée
fusion ([1,3,5,8,9],[0,2,7]) → [0,1,2,3,5,7,8,9]

► Exemple : tri par fusion

Pourquoi utiliser la programmation récursive ?

La programmation récursive est-elle plus simple que la programmation itérative ?

Oui, souvent, car elle est « naturelle ».
Peut-on toujours passer facilement de l’une à l’autre ?
Non.
La plupart des traitements itératifs simples sont facilement traduisibles sous forme récursive (exemple du for).
L’inverse est faux. Il arrive même qu’un problème ait une solution récursive très simple alors qu’il est très difficile d’en trouver une solution itérative.

► Exemple : On peut utiliser la récursivité pour trouver un chemin jusqu’à une case donnée dans un labyrinthe.

Pour une case d’arrivée donnée (forme récursive) :

• Il existe un chemin qui part d’une case donnée si et seulement s’il existe un chemin qui part d’une cases voisines — non encore explorée, pour que la taille du problème diminue à chaque étape. Chaque case rencontrée sera marquée comme ayant été visitée.
• On a réussi si la case de début est voisine de la case d’arrivée ; il n’y a pas de chemin si l’on a exploré (récursivement) sans succès toutes les cases voisines de la case de départ.

voisins(L,debut) : renvoie la liste des cases voisines non visitées

Renvoie True si un chemin est trouvé, et False sinon.
Le labyrinthe L est modifié (ajout de couleurs).