Comment ça marche: La recursivité
Ç’est quoi la récursivité? Supposons que vous soyez assis dans un théâtre et que vous souhaitiez vérifier le numéro de votre rangée, que feriez-vous? Une possibilité est de demander à la personne en face de vous, qui demanderait à la personne en face de lui et ainsi de suite jusqu’à ce que la personne de la première rangée soit atteinte. Ensuite, chaque personne dira à celui qui se cache derrière son numéro et vous pourrez récupérer le vôtre. Voilà, ceci est le principe de base de la récursivité, que l’on détaillera ici.
En mathématique et en informatique, une classe des objets ou des méthodes est défini de manière récursive si ces 2 propriétés sont satisfaites :
=> Un scenario pour terminer l’algorithme (case terminal ou case de base)
=> La réduction d’un problème vers un autre plus petite
Dans notre exemple, la distance initiale entre nous et notre cible est de n pas. Avec un appel récursif, on diminue le nombre d’étapes nécessaires à n-1, puis n-2, jusqu’à 0. À ce moment là, le cas terminal est utilisé. Celui-ci est un algorithme récursif direct parce qu’on a rappelé la même fonction pour simplifier notre problème vers le cas terminal. Cependant, il existe d’autres types d’algorithmes récursifs.
On peut distinguer plusieurs classes d’algorithmes en fonction du :
- Le mode d’appel : direct/indirect
- Le nombre de paramètres utilisés : arité
- Le nombre d’appels : l’ordre de récursion
Pour mieux comprendre ce qui se cache derrière chaque catégorie on prendra des exemples de pseudo-code :
1. Le mode d’appel
Un exemple classique de récurision est représenté par le calcul de la valeur de factorielle de n, ou n ! = n x (n-1) x (n-2) x … x 1.
Ici on utilise une fonction qui contient 2 possible instructions: l’exécution du cas terminal (si n est plus petit ou égal à 1) ou la réduction vers un problème plus petite (calcul de factorielle de n-1). Cela représente un algorithme récursif direct parce qu’on appelle la fonction lui-même chaque fois.
2. Le nombre de paramètres utilisés
L’arité représente le nombre d’entrées qui sont modifiées suite aux appels récursifs. On peut observer cet aspect dans l’exemple d’un algorithme qui calcule le PGCD (Plus Grand Commun Diviseur).
Nos paramètres d’entrée sont a et b qui sont modifiées chaque fois qu’ils ne sont pas égaux ou nuls. Comme à chaque appel récursif a ou b est décrémenté, cet algorithme va s’arrêter que lorsqu’une des 2 conditions est satisfaite.
3. Le nombre d’appels
Les algorithmes vus jusqu’a présent ont un ordre égal à 1 comme ils ont besoin de calculer seulement une instance d’une valeur par appel. Il est aussi possible d’avoir des algorithmes qui font plusieurs appels récursifs pour calculer une valeur à un moment donné, par exemple la série de Fibonacci.
Pour cet exemple, la série commence avec F0 = 1 et F1 = 1 et continue avec la somme des 2 dernières valeurs. Comme n diminue constamment, on peut observer que l’algorithme s’arrêt après l’appel quand n = 2 parce que les 2 cas de base seront exécutés. À partir de cet algorithme on détaillera l’effet de chaque appel dans la mémoire et comment chacun est empilé.
Comme le résultat d’un appel récursif dépend d’un autre, il est nécessaire de sauvegarder toutes les étapes intermédiaires entre le point de départ et le cas terminal. Pour réaliser cela, on est obligé d’enchaîner les étapes dans une pile (un type abstrait de données qui repose sur le principe : dernier entré, premier sorti) durant tout le procès. Dans l’exemple de la suite de Fibonacci on peut observer qu’on a besoin de 2 piles comme c’est un algorithme d’ordre 2. On va empiler (rajoute un nouveau récursion) jusqu’à arriver au cas terminal. À ce moment là on va dépiler (retourner la valeur dans l’appel antérieur) pour obtenir le résultat voulu. Le schéma ci-dessus illustre le principe :
Comment optimiser un algorithme récursif ?
Pour améliorer le coût mémoire, on peut écrire notre algorithme de méthode récursive terminale. Cette implémentation permet d’effectuer l’appel récursif seulement dans la dernière instruction évalué. La fonction ne fait rien après un appel sauf si c’est le cas terminal. Ce paradigme est utile parce qu’on n’a pas besoin d’attendre le résultat, on peut directement le passer. Également, on évite la consommation d’espace dans la pile. Nous allons ensuite comparer deux algorithmes récursifs pour calculer la fonction factorielle.
Dans l’exemple récursif non-terminal, à chaque appel on empile jusqu’à arriver au cas terminal. Après on envoie la nouvelle valeur du bas vers le haut pour obtenir le résultat. Ainsi, à chaque appel on effectue un nouveau calcul.
Le deuxième exemple présente le même algorithme écrit de façon récursive terminale. La différence est qu’au lieu d’effectuer le calcul à chaque pas, l’algorithme transpose un tel problème dans un autre plus proche du cas de base. Cette action est efficace du point de vue du coût de mémoire parce que tous les calculs sont effectués par modification des paramètres et on ne doit pas consommer d’espace de pile. Autrement dit, un algorithme récursif terminal utilise un espace en mémoire constant, comme un algorithme itératif (qui contient une boucle).
La récursivité est massivement utilisée dans les structures de données récursives (listes, arbres, graphes). Pour cette raison la plupart des langages de programmation permet l’utilisation des deux, il existe aussi des langages comme Haskell qui sont dédiés uniquement au paradigme fonctionnel (en utilisant une fonction qui s’appelle elle-même de façon récursive). Le choix reste au développeur pour décider quelle implémentation est plus efficace.
[1] Wikiversity
[2] Utah.edu
[3] Openclassrooms
[4] Stackoverflow
[5] Quora
