Programmation

Optimisez votre code grâce à la récursivité

 

En algorithmie, on qualifie de récursive toute fonction ou méthode qui s’appelle elle-même dans sa propre définition. Ceci est utile lorsque l’on a besoin de répéter une action pour obtenir un résultat. Une fonction qui ne s’appelle pas elle-même pour exécuter la même tâche est dite itérative. Il est facile de comprendre le principe de fonctionnement de ces deux styles de programmation lorsque l’on connaît le sens de leurs étymologies latines. Recursio désigne l’action de revenir en arrière tandis que iterum signifie « encore une fois », il en découle que l’une a besoin de revenir à elle et se ré-utiliser, tandis que l’autre se contente de répéter ce qu’elle doit faire dans une boucle.

Je parle d’optimisation dans le titre, mais il ne faut pas en déduire que l’une est supérieure à l’autre. Il y a juste des situations où utiliser le principe de récursivité vous sera plus favorable. Jusqu’ici, la plupart d’entre vous est familier à l’itérativité et vous trouvez peut-être que la récursivité est contre-intuitive. Ne vous inquiétez pas, pour que cela semble plus naturel, je commencerai par une analogie avec les mathématiques que vous avez peut-être d’avantage l’habitude de manipuler. Aussi, tout l’article sera rédigé dans un langage formel simple et concis, il va de soi que les algorithmes sont retranscriptibles dans pratiquement n’importe quel langage !

Une première approche

Le cas d’école que l’on présente toujours en premier est la fonction factorielle. En mathématiques elle est notée n! (lire factorielle de n) et est définie pour tout entier naturel n par :

n! = n*(n-1)! et 0! = 1

Pour les moins matheux d’entre vous, considérez l’exemple suivant :

5! = 5*4*3*2*1 = 5*(4!) = 5*(4*3*2*1) = 5*(4*(3!)) = etc...

Notez que ce sont les deux conditions qui définissent la fonction, si l’on ne sait pas que factorielle de 0 donne 1, on ne peut pas calculer factorielle de 1, et donc on ne peut calculer celle de 2 et ainsi de suite. En revanche, comme il s’agit d’une fonction définie sur les entiers naturels, zéro est le dernier terme possible, il est donc inutile de connaître un terme plus petit pour le calculer.

Pour coder la fonction factorielle, ceux qui n’ont jamais entendu parler de récursivité utiliseraient assez intuitivement une boucle itérative comme celle qui suit :

fonction Factorielle( n : un entier ){
--> soit i, un entier
--> soit resultat = 1, un entier
--> pour i allant de 1 à n faire :
      --> resultat = resultat * i
--> fin pour
--> retourner resultat
}

Il s’agit d’utiliser une boucle for qui multiplie un résultat par un entier i allant de 1 jusqu’à n, la condition d’arrêt qui empêche la boucle d’être infinie étant l’atteinte de ce dit n. Il est beaucoup plus simple de définir cette fonction de manière récursive car quand on relit la définition mathématique on constate qu’en effet, la fonction s’utilise elle-même dans sa définition ! En revanche il ne faut pas oublier de définir la condition d’arrêt, sinon à l’instar d’une boucle infinie, on peut tomber dans un récursion infinie qui provoquera un débordement de la pile d’exécution. Nous l’avons vu précédemment, la condition 0! = 1 est primordiale car zéro constitue le dernier terme de la suite du calcul. Il s’agit en fait de la condition d’arrêt, voyez ci-dessous :

fonction Factorielle( n : un entier ){
--> si n = 0 retourner 1
--> sinon retourner n*Factorielle(n-1)
}

Wow, quel gain de lignes nous avons là ! La fonction est à présent la parfaite traduction en langage formel de sa définition mathématique. Vous avez du mal à visualiser comment elle marche ? Essayez de compiler à la main Factorielle(5) et vous obtiendrez exactement la même logique que l’exemple mathématique utilisé précédemment :

  1. Factorielle(5) :  5 n’est pas égal à 0 donc on retourne 5*Factorielle(5-1).
  2.  5*Factorielle(4) : 4 n’est pas égal à 0 donc on retourne 4*Factorielle(4-1).
  3. 5*4*Factorielle(3) : 3 n’est pas égal à 0 donc on retourne 3*Factorielle(3-1).
  4.  etc..
  5.  etc…
  6. 5*4*3*2*1*Factorielle(0) : tiens voilà notre condition d’arrêt ! On retourne 1.

Et voilà 5*4*3*2*1*1 nous avons un résultat total de 120, qui est bien 5!. Comme vous pouvez le constater cette méthode nous à coûté n+1 récursions, tandis que la version itérative nous mange uniquement n itérations. Bah alors, la récursivité est-elle moins efficace que l’itérativité ? Non, on a gagné en lignes et en simplicité, on n’utilise ni variable temporaire ni structure de contrôle comme la boucle for, c’était l’optimisation recherchée dans ce cas précis d’implémentation ! De plus, on pourrait définir la condition d’arrêt comme étant 1! = 1 et épargner un appel récursif à notre programme, mais bon je voulais être rigoureux par rapport à la véritable définition mathématique, désolé… mes profs de maths sont si pointilleux sur la rigeur que j’en ai des troubles post-traumatiques.

Une définition plus concise

Pour définir une fonction récursive on a donc besoin de deux choses :

  • Un principe de récursion.
  • Une ou plusieurs condition.s d’arrêt.

On peut définir le motif général d’une fonction récursive comme ceci :

fonction MaFonction(argument1, ...,argumentn) {
--> si condition d'arrêt retourner resultats
--> sinon retourner (calcul ou expression)MaFonction(argument_bis1, ...,argument_bisn)
}

Quand et pourquoi privilégier une approche récursive

Comme je l’ai répété moultes fois, la récursivité et l’itérativité ne sont pas des concurrentes, elles sont complémentaires. Il faut savoir dans quels contextes il est possible et favorable d’utiliser l’une ou l’autre.

Quand ?

La réponse est évidente, on ne peut pas utiliser une fonction récursive pour réaliser une tâche qui n’a pas besoin d’évaluer plusieurs fois le même type de tâches. Je veux dire par là que si nous avons besoin d’effectuer des opérations différentes à chaque fois pour parvenir à nos fins, on utilisera une fonction contenant peut-être une boucle et un florilège d’autres outils. En contre-partie, si pour exécuter une tâche on a besoin au préalable d’effectuer plusieurs sous-tâches de même nature, il est possible de concevoir un modèle d’exécution récursive.

Si vous vous posez la question, oui en dehors des mathématiques, on peut être face à ce genre de problème. Par exemple, quand on code une intelligence artificielle pour un Morpion (Tic Tac Toe pour ceux qui baignent dans un monde trop américanisé), il faut parcourir un arbre représentant tous les coups possibles et chaque noeud de l’arbre possède un poids qui détermine son efficacité. Je n’ai jamais essayé de coder ce type de jeu, mais j’imagine qu’on pourrait essayer dans une version simple une fonction comparant deux noeuds et retournant le coup le plus judicieux comparé au noeud voisin s’il existe, la condition d’arrêt étant d’avoir comparé tous les noeuds se trouvant sur un même niveau de profondeur. On jouerait ensuite le coup choisi et ainsi de suite. Ceci n’est qu’un exemple parmi tant d’autres, et vous pouvez vous amuser à en trouver des bien plus complexes !

g5725
Exemple.

Pourquoi ?

Si un algorithme récursif n’est pas plus rapide que sa version itérative pourquoi l’utiliser ? La performance n’est pas un objectif primordial pour un développeur, il est nécessaire de se pencher dessus lorsqu’un ralentissement conséquent du programme empêche une bonne utilisation. Par exemple quand je fais une mission infectée sur Warframe, plus il y a d’ennemi à l’écran, plus je lag et je rage. En vérité c’est parce que j’ai un processeur et une carte graphique aussi naze l’un que l’autre, mais il est vrai qu’il faut toujours avoir un nombre minimum d’objets actifs en même temps afin de consommer un minimum de ressources. Dans ce cas là, la performence est une priorité, mais la plupart du temps l’utilisateur ne se rendra même pas compte que le programme exécute telle ou telle tâche plus lentement qu’il ne le pourrait. Ce que l’on vise, c’est la simplicité.

Parfois il est tout simplement plus lisible d’écrire une fonction récursive, on la comprend mieux, elle est plus facile à modifier ou à utiliser dans d’autres fonctions, elle est plus proche de la définition réelle de la tâche à exécuter (comme la factorielle récursive qui suit exactement la définition mathématique)… et puis parfois non. C’est pourquoi il faut être au courant des deux possibilités et s’entraîner à utiliser les deux méthodes pour déterminer le meilleur choix au bon moment !


Sources :
Mon cours d’algorithmie à l’université
Le wiktionnaire pour les locutions latines

Le cours de Developpez.com

Le cours d’OpenClassroom

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s