Introduction
Déjà près de 8 mois que je suis en poste au sein de l’entreprise et encore aujourd’hui, je ne cesse de découvrir de nouvelles choses. La dernière en date : Les fonctions récursives, et plus globalement, la récursivité. Bien qu’un peu effrayant de par son appellation, le concept est en fait assez simple dans son principe même s’il nécessite peut être de comprendre comment le langage Javascript est exécuté dans les environnements d’exécution que sont par exemple les navigateurs web ou Node JS.
Au sein de cet article les ami(e)s codeurs, nous allons explorer le concept de récursivité. Au sein de cet article les ami(e)s codeurs, nous allons explorer le concept de récursivité. Au sein de cet article les ami(e)s codeurs, nous allons explorer le concept de récursivité. (Vous comprendrez à la fin de l’article…)
Concept
Pour bien comprendre avant tout le concept de récursivité, il faut comprendre qu’elle est présente au sein de certaines de nos actions sans même nous en rendre compte. Ce genre de moment ou l’on répète une même logique jusqu’à atteindre l’objectif désiré au départ.
Parcourir un dictionnaire est une bonne illustration de la récursivité. On cherche un mot en particulier et on ne s’arrête que lorsque on est arrivée à la bonne page du dictionnaire pour lire sa définition. Tant que ce n’est pas le cas, on vérifie la page du dictionnaire au sein de laquelle nous sommes, on détermine si nous sommes en avance ou en retard dans l’alphabet par rapport au mot que l’on recherche et en fonction de cela on ouvre une nouvelle page du dictionnaire dans la bonne direction. Et on recommence cette logique. Encore. Encore. Encore.
C’est le concept de récursivité.
Fonction itérative vs. fontion récursive
Lorsque l’on parle de récursivité en programmation, on parle en fait de la capacité d’une fonction à s’appeler elle-même.
Imaginons que nous souhaitons par exemple créer une fonction qui va permettre de calculer le produit de tout les nombres inférieurs et égaux à un entier prédéfini n. On appelle cela la factorielle d’un nombre. C’est un exemple parfait pour illustrer le concept de récursivité.
Un tel programme peut être implémenter entre autre de deux façons différentes : A l’aide d’une fonction itérative (qui utilise les boucles) et à l’aide d’une fonction récursive (qui utilise la récursivité).
Mais alors quelle est la différence entre ces deux fonctions ? Car bien qu’utilisant une logique différentes, les deux fonctions renvoient le même résultat avec un même argument fourni en entrée de ces dernières. En effet, le résultat de ces deux fonctions auxquelles on fournit l’argument de valeur 3 serait identique, à savoir la valeur 6.
La vraie différence réside justement dans leur logique respective différente, dans la façon dont elles sont construites pour répondre au problème et donc dans le déroulement de l’exécution qui en découle.
Javascript est un langage monothread. Cela signifie que son exécution se déroule à l’aide d’une seule et unique structure de données que l’on nomme généralement call stack. Ainsi, au fur et a mesure de l’exécution du programme, les logiques internes de celui-ci se succèdent unes à unes dans cette call stack pour arriver au résultat désiré, entrant dans cette dernière puis la quittant une fois la logique exécutée.
Pour rendre cela plus clair reprenons les exemples de nos deux fonctions. Souvenez vous que celles-ci renvoient le même résultat. Et regardons comment un navigateur Web ou Node JS, et donc la call stack qu’ils renferment, se charge de les exécuter en leur fournissant un argument de valeur 3.
Au sein d’une fonction itérative, toute la logique qui y réside est interne à la fonction. Autrement dit, celle-ci ne fait appel a rien “d’extérieur”. Ainsi, la fonction est appelée au sein du programme avec l’argument de valeur 3 et rejoint donc la call stack de l’environnement d’exécution. Une fois la boucle au sein de cette fonction terminée, celle-ci quitte la call stack et retourne le résultat, la valeur 6.
Comme vous pouvez le voir, la fonction récursive est exécutée elle de manière totalement différente. En effet, tant qu’elle ne respecte pas la condition défini pour l’argument fourni en entrée elle continue de s’appeler elle même en modifiant cet argument. C’est la phase ascendante de remplissage de la call stack que l’on aperçoit.
Une fois la condition valide, dans notre cas un argument égale à la valeur 0, alors on retourne la valeur 1 et la fonction quitte la call stack. Mais celle-ci n’est pas retourné en résultat du programme, elle est transmise à l’instance précédente de la fonction, qui elle va faire de même, entraînant le vidage progressif de la call stack jusqu’à ce que la dernière présente renvoie le résultat du programme. Encore une fois, la valeur 6.
C’est la phase descendante de vidage de la call stack que l’on aperçoit. La logique successive d’appel de la fonction et du calcul qui se déroule peut être représenté plus simplement d’une autre manière.
Limites et cas d’utilisation
Forcément, le comportement de la récursivité peut alors devenir très consommateur en terme de besoin mémoire de la machine. En effet, contrairement à la fonction itérative qui n’implique qu’une seule instance de la fonction dans la call stack de l’environnement d’exécution, chacune des instances de la fonction récursive nécessite l’allocation d’une partie des ressources de la machine qui exécute le programme.
Imaginez seulement devoir exécuter cette fonction avec en entrée un argument d’une valeur de 10 000…
Face à ce constat difficile peut être de voir les avantages que peuvent procurer l’utilisation de la récursivité par rapport à la simple itération. Mais en terme d’utilisation, la fonction récursive peut répondre à des cas précis.
Son utilisation peut être intéressante dans les cas où le nombre d’itération est minimes comme dans notre exemple. Par ailleurs, cela n’est qu’une question d’appréciation personnelle mais la fonction récursive peut apporter une certaine lisibilité du code. De par sa structure, celle-ci est effectivement souvent d’une relative simplicité dans sa compréhension dès lors que l’on comprend comment fonctionne la récursivité.
Il faut bien comprendre que le principe de la récursivité est de découper un problème en sous tâche multiples.
Ainsi La récursivité peut être utilisé dans de nombreux cas de recherche et de tri. Notre exemple de parcourt d’un dictionnaire est d’ailleurs un semblant de ce que l’on nomme la recherche binaire et celle-ci peut être implémenté à travers l’utilisation de la récursivité. Il est d’ailleurs également souvent utilisés pour effectuer des traversée dans des arbres, des structures de données spécifique qui s’accordent parfaitement à ce concept.
Finalement, dès lors que le problème et sa solution implique la répétitivité d’une logique, la récursivité peut être une solution à ce problème.
Implémentation récursivité
En Javascript, comme dans d’autres langages, la récursivité est implémenté à travers l’appel à une fonction au sein de cette même fonction, généralement en lui fournissant à chaque fois des arguments différents jusqu’à qu’une condition soit rencontrée.
Afin d’écrire une fonction récursive en Javascript, il faut définir les deux parties qui compose celle-ci: Le cas de base et le cas récursif.
Le cas de base consiste à définir la logique, la condition qui va mettre fin à la boucle de récursion de la fonction. Qui va mettre un terme aux appels de la fonction. Son implémentation est très importante car à l’instar d’une boucle, si mal défini, cela peut mener à un appel infini encore et encore de la fonction et donc a un manque de ressource de la machine qui exécute la fonction.
le cas récursif, lui, permet de définir la condition qui implique le nouvel appel à la fonction avec le nouvel argument si le cas de base n’est pas vérifié. C’est cette logique qui est alors effectivement répété. Ici aussi, il est très important de bien définir les nouveaux appels à la fonction. En effet, un appel mal défini, notamment au niveau du nouvel argument fourni, peut également poser des non-sorties.
Pour bien utiliser la récursivité et écrire des fonctions récursives efficaces, il est important de suivre des pratiques précises. Ainsi on s’assure d’un code efficace, maintenable et facilement débuggable.
Conclusion
La récursivité, si utilisée dans les bons cas, est un outil du langage de programmation Javascript qui peut s’avérer vraiment puissant et élégant grâce à sa capacité de simplification des problèmes. Il est cependant important selon moi les ami(e)s codeurs de bien comprendre son fonctionnement et sa structure pour l’implémenter de manière correct et à bon escient.
En effet, les fonctions récursives ne conviennent pas forcément à tout les types de problèmes et sa gourmandise en terme de ressources de la machine les prédestinent plutôt a des cas ne nécessitant qu’un faible nombre d’itération.
Plonger dans la compréhension de la récursivité possède également un vrai intêret pour comprendre le principe d’exécution d’un programme Javascript au sein d’un environnement d’exécution.
