Fiche de révision : Algorithme récursif

Principe général

• Les fonctions peuvent comporter un ou plusieurs appels à d’autres fonctions.
• La récursivité est la capacité d’une fonction à s’appeler elle-même.
• Si nous modifions notre fonction accueil() en ajoutant un appel à elle-même dans sa définition, après l’appel à print() : l’ordinateur va produire un grand nombre d’affichages (quelques milliers de ligne) avant d’afficher une erreur.
• Abstraction faite de l’erreur, notre fonction a bien réussi à s’appeler elle-même, produisant un comportement assez analogue à celui d’une boucle infinie.
• Si on reproduit la même expérience en conférant un paramètre à la fonction, là encore une erreur s’affiche après quelques milliers de lignes, mais on constate que l’argument passé en paramètre a bien été pris en compte.
• Notre fonction est récursive : elle s’appelle elle-même, elle s’auto-référence.
• Une fonction récursive se compose de deux parties :
• une partie récursive qui comporte un appel récursif (ce qui permet à la fonction de s’auto-référencer) ;
• une partie terminale qui définit les conditions de terminaison de la fonction (ce qui permet de stopper les appels récursifs quand une condition est atteinte).
• Si la partie terminale est manquante, la fonction s’appelle un nombre infini de fois.
• Si la partie récursive est manquante, la fonction n’est pas récursive.
• On veut définir de manière récursive une fonction qui raccourcit une chaîne de caractères pour n’en conserver que la première lettre :
• la partie terminale vérifiera si la condition voulue est atteinte : une chaîne de caractères qui en comporte un seul ;
• la partie récursive effectuera un appel à la fonction avec en paramètre une chaîne de caractères tronquée de son caractère final, et en retournera le résultat.
• Si nous appelons la fonction avec une chaîne vide avec print(raccourcit('')), son exécution durera plusieurs secondes et finira par générer une erreur de type RecursionError car comme la troncature du dernier élément d’une chaîne vide est une chaîne vide, l’appel récursif n’évoluera pas et s’effectuera en permanence sur une chaîne vide.
• Dans ces conditions la fonction n’atteindra jamais la condition terminale où la longueur de chaîne est de longueur $1$.
• Une légère modification de la partie terminale de notre fonction permet de pallier ce problème : au lieu d’une égalité stricte, nous retournons toute chaîne de longueur inférieure ou égale à $1$ caractère.

Fonctionnement récursif

• Dans cette partie nous nous intéressons à la manière dont l’interpréteur Python gère la récursivité, on peut l’illustrer en s’appuyant sur l’exemple du calcul de la factorielle $5!$.
• $5! = 5\times{4}\times{3}\times{2}\times{1}$
  $5! = 5\times{4!}$
  or $4! = 4\times{3!}$
  de la même manière $3! = 3\times{2!}$ et $2! = 2\times{1!}$
  et par définition $1!= 1$
• Nous disposons des éléments requis pour implémenter une version récursive du calcul de la factorielle d’un nombre :
• la partie terminale est $1! = 1$ ;
• la partie récursive s’applique ainsi à tout $n > 1$ :
  $n! = n\times{(n - 1)!}$
• L’implémentation en Python en est une transcription assez littérale.
• Notre fonction produit bien le résultat attendu :
  print(factorielle_recursive(5))
  # affiche 120
• On pourra modifier notre condition terminale : if nombre == 1: en if nombre <= 1:.
• Cela nous permet de calculer $0!$ (égal à $1$), mais aussi d’empêcher des appels récursifs pour des nombres négatifs qui conduiraient à une RecursionError.
• Afin de pouvoir suivre le fonctionnement de notre programme récursif, nous insérerons des affichages à différents endroits.
• On observera alors des appels en cascade : chaque calcul de la factorielle d’un nombre donné reste suspendu en attente du résultat de celle de valeur immédiatement inférieure.
• Le mécanisme qui permet de suivre ces appels successifs et les retours attendus s’appelle une pile d’exécution.
• La pile d’exécution (LIFO) empile les appels de fonction successifs correspondant aux cas récursifs, permettant à l’interpréteur Python de garder la trace des appels individuels.
• Une fois le cas terminal atteint, la pile est progressivement dépilée et chaque appel reçoit en retour le résultat qu’il attendait.
• Ces appels étant potentiellement gourmands en mémoire, les langages qui permettent la récursivité de fonctions ou de programmes limitent le nombre d’appels récursifs.
• En Python le débordement de pile génère l’erreur spécifique RecursionError.

Implémentations récursives

• Il existe différents types d’implémentations récursives. Les exemples que nous avons présentés jusqu’à présent étaient des cas de récursivité simple, mais la récursivité peut prendre d’autres formes.

• L’implémentation récursive n’est pas une obligation mais un choix : tout algorithme itératif peut être écrit en récursif et vice-versa.
• Ce choix dépend de plusieurs facteurs :
• la facilité d’implémentation ;
• les contraintes de mémoire et de performance ;
• la nature des données sur lesquelles les traitements sont effectués ;
• l’aisance du·de la développeur·se avec l’une ou l’autre approche ;
• les pratiques logicielles en vigueur dans une organisation ou un secteur d’activité.
• La récursivité étant possible dans tous les langages de programmation généraliste et implémentée dans un certain nombre d’algorithmes, tout·e développeur·se doit connaître et maîtriser les bases de la récursivité.