Qu’est-ce que la récursivité en programmation et comment l’utilisez-vous ? –
La récursivité est une partie importante de la programmation fonctionnelle qui peut aider à résoudre des problèmes complexes avec des solutions élégantes. Cependant, il est important de comprendre les avantages et les inconvénients afin que cela puisse être fait correctement.
Sommaire
Qu’est-ce que la récursivité ?
La réponse courte est que la récursivité est fondamentalement chaque fois qu’une fonction s’appelle, généralement avec une entrée différente passée à la fonction enfant. Il s’appelle encore et encore jusqu’à ce qu’une condition de sortie soit atteinte, puis transmet les résultats dans la pile d’appels, les modifiant potentiellement au fur et à mesure.
La réponse longue est que la récursivité peut aider à résoudre des problèmes compliqués en les décomposant en sous-ensembles plus petits du problème principal. Souvent, vous aurez des structures de données contenant des données imbriquées. La décomposition en plus petites quantités de données facilitera le traitement.
Par exemple, supposons que chaque feuille de l’arbre ait une valeur associée et que nous voulions trouver la somme de toutes les valeurs. Nous pourrions le faire avec une fonction comme la suivante, qui parcourt l’arbre feuille par feuille, inspectant tous les enfants et calculant le total.
int CountAllLeaves(Leaf currentLeaf) { // Start with the current value int Total = currentLeaf.value; // Add any children to the value, if any foreach(Leaf childLeaf in currentLeaf.children) { Total = Total + CountAllLeaves(childLeaf); } return Total; }
Cela fonctionne parce que CountAllLeaves ne se soucie pas de la feuille avec laquelle vous l’appelez. Il s’appelle à plusieurs reprises jusqu’à ce qu’il atteigne la dernière feuille de l’arbre, qui n’a pas d’enfants. Pour cette raison, il renvoie simplement sa propre valeur. Cette valeur est transmise à la feuille parent, qui ajoute la valeur de l’enfant à la sienne, puis se répète pour tous les frères et sœurs de cette feuille enfant. Au final, le résultat final de la fonction sera la somme totale de toutes les feuilles de l’arbre.
À un moment donné, vous devez atteindre le cas d’arrêt, qui est la partie du problème dont vous connaissez la réponse sans faire d’appels plus récursifs. Sinon, la fonction bouclerait indéfiniment, provoquant le plantage du programme. Dans ce cas, le cas d’arrêt est lorsque la fonction atteint une feuille qui n’a pas d’enfant.
Il ne doit pas s’agir de structures de données imbriquées comme des arbres. Vous pouvez écrire des fonctions récursives autour de tout type de problème. Par exemple, calculer la factorielle d’un nombre consiste à le multiplier par chaque nombre plus petit que lui. Vous pouvez le faire très facilement avec la récursivité :
int Factorial(int n) { if (n <= 1) return 1; return n * Factorial(n-1); }
Dans cet exemple, le cas d’arrêt est lorsque n
atteint 1, où il renvoie finalement une valeur et la pile d’appels peut être réduite.
Regardons un exemple du monde réel. Dans ce bout de code, il y a un Container
classe qui contient plusieurs éléments d’interface utilisateur qui lui sont attachés, ainsi que plusieurs conteneurs enfants avec leurs propres éléments. Il doit être « rendu » en une liste plate d’éléments pouvant être affichés à l’écran.
Il s’agit essentiellement d’une autre structure de données arborescente, l’approche est donc similaire. Sauf que, dans ce cas, la variable totale est une liste, à laquelle sont ajoutées les listes d’éléments de chaque conteneur.
La magie de le faire en utilisant la récursivité est qu’elle préserve l’ordre Z des éléments. Les éléments dessinés après d’autres éléments vont en haut, de sorte que le plus jeune conteneur enfant s’affichera toujours en haut. Dans ce scénario, j’ai également trouvé utile d’afficher les éléments de superposition, qui sont ajoutés une fois que les autres éléments et les enfants ont terminé le rendu.
Les dangers de la récursivité
Alors, quand devriez-vous utiliser la récursivité dans votre code ? La réponse est que vous devriez probablement l’éviter dans la plupart des situations, en particulier lorsqu’une solution itérative utilisant une simple boucle fera le travail.
Chaque fois que vous appelez une fonction, votre programme alloue des ressources à cette fonction. Toutes les variables et informations locales vont sur la pile, qui est une structure de données Last-In, First-Out (LIFO). Cela signifie que le dernier appel de fonction est toujours le premier à être supprimé, comme un compartiment où vous supprimez toujours l’élément supérieur.
Le problème avec la récursivité est qu’elle peut utiliser un appel de fonction imbriqué pour chaque élément en cours de traitement. Cela entraîne beaucoup plus de surcharge, car chaque appel de fonction a besoin de son propre ensemble de variables et de paramètres locaux. Cela prendra un temps de traitement supplémentaire par rapport à une approche basée sur une boucle.
Les boucles n’ont pas ce problème. Après chaque itération de boucle, la pile aura l’élément supérieur effacé. Il pourrait traiter un milliard d’éléments en utilisant la même pile.
Si vous utilisez trop de ressources avec des appels de fonction récursifs, cela peut entraîner débordement de pile, où le programme peut planter simplement en raison d’un trop grand nombre d’appels imbriqués. Cela peut se produire avec des ensembles de données particulièrement volumineux ou avec des algorithmes médiocres comme la récursion binaire ou exponentielle, qui s’appellent plusieurs fois par appel de fonction.
Utiliser la récursivité avec parcimonie
La récursivité est une bonne chose à avoir pour certains problèmes, mais il n’y a fondamentalement pas de solutions récursives aux problèmes qui ne peuvent pas également être résolus à l’aide de boucles (sauf pour la récursion imbriquée comme la fonction d’Ackerman). Même les structures de données arborescentes complexes peuvent être parcourues à l’aide de boucles et de piles. Si vous devez gérer de grandes quantités de données ou si vous vous souciez beaucoup des performances, vous feriez peut-être mieux d’utiliser une solution itérative.
L’autre problème avec la récursivité est qu’elle peut conduire à un code difficile à comprendre pour d’autres personnes, car il faut généralement se gratter la tête avant que quelqu’un l’obtienne. Bien que cela semble souvent être la solution la plus «élégante», votre travail en tant que programmeur n’est pas de vous montrer, mais plutôt d’écrire du code fonctionnel et lisible.
Dans tous les cas, vous voudrez vous demander s’il serait préférable d’utiliser une boucle pour résoudre le problème. La récursivité devrait être votre dernier recours pour des problèmes qui seraient beaucoup plus compliqués sans elle. En fait, dans l’ensemble de mes 40 000 lignes de code source, je n’avais qu’un seul exemple de récursivité pour cet article.
Et, après un deuxième coup d’œil, j’ai remarqué un problème. Bien qu’il ait bien fonctionné, il a été écrit de manière paresseuse et évidente et, en tant que tel, utilise beaucoup plus de mémoire qu’il n’en a besoin. Ce n’est pas vraiment un problème avec les petites structures de données qu’il gère, mais cela créait un new List<CuiElement>()
pour chaque appel de la fonction, et en ajoutant les résultats des enfants en dessous. Cela signifiait que si on lui donnait un conteneur avec des enfants profondément imbriqués, il stockerait les mêmes données encore et encore sans raison.
La solution dans ce cas était de passer à la fonction récursive une référence à une liste externe, et d’y ajouter directement tous les éléments. Cela impliquait également de changer le Render()
en une fonction qui gérait la configuration de niveau supérieur pour la fonction de construction récursive.
Cela accomplit exactement la même solution consistant à ajouter chaque élément dans le bon ordre, mais résout le problème de l’utilisation de la mémoire qui augmente de façon exponentielle à chaque appel.
Néanmoins, je suis satisfait de cette fonction car elle est assez concise et fait le travail facilement. Si je devais convertir cela en une solution à l’aide d’une boucle, ce serait beaucoup plus compliqué et ferait exactement la même chose. Vous devrez peser le pour et le contre de l’utilisation d’une solution récursive et ne les utiliser que là où vous ne vous attendez pas à une utilisation sérieuse des ressources. Dans ce cas, je ne m’attends pas à appeler cette fonction avec des conteneurs imbriqués contenant des centaines d’éléments, donc utiliser la récursivité ici est très bien.
Pour plus d’informations sur ce sujet, consultez notre guide sur la récursion.