J'aime la récursion. Je pense qu'elle simplifie beaucoup les choses. D'autres peuvent ne pas être d'accord ; je pense aussi que cela rend le code beaucoup plus facile à lire. Cependant, j'ai remarqué que la récursion n'est pas autant utilisée dans des langages comme le C# qu'en LISP (qui est d'ailleurs mon langage préféré à cause de la récursion).
Quelqu'un sait-il s'il y a de bonnes raisons de ne pas utiliser la récursion dans les langages tels que C# ? Est-elle plus coûteuse que l'itération ?
Sont-ils plus chers que itérations ?
Oui, ils le sont. De nombreuses variantes de Lisp supportent l'idée d'une "optimisation tail-call" qui permet de convertir de nombreuses utilisations d'un appel de fonction récursif en un appel itératif (en simplifiant un peu). Si le tail-call n'est pas supporté, alors un appel de fonction récursif utilisera progressivement plus de mémoire sur la pile.
Sont-ils plus chers que itérations ?
Oui, ils le sont. La récursion nécessite la création d'un nouveau cadre de pile ainsi qu'un appel et un retour, alors que l'itération ne nécessite généralement qu'une comparaison et un branchement, ce qui la rend nettement plus rapide. Toutefois, les compilateurs peuvent effectuer une optimisation de l'appel de queue sur certains appels récursifs (à savoir les appels de queue), ce qui leur permet de réutiliser le cadre de pile, rendant l'appel récursif beaucoup moins coûteux et le transformant effectivement en itération. Scheme exige en fait que les compilateurs de scheme implémentent l'optimisation tail-call.
Le compilateur et l'architecture des CPU modernes peuvent effectuer de nombreuses optimisations avec l'itération qu'ils ne peuvent pas faire avec la récursion. Par exemple, la capacité du processeur à effectuer des calculs optimistes. Lorsque le processeur trouve un espace d'itération, il sait combien de temps cela va prendre. Dès le début, il n'y a pas vraiment besoin de vérifier chaque fois avant de commencer la boucle suivante. Donc, on pipeline les opérations. Comme la plupart des processeurs peuvent effectuer plusieurs opérations en même temps (grâce au pipelining), vous pouvez résoudre l'espace d'itération en moins de temps que la récursion. Ceci même avec l'optimisation de la queue, car le CPU traite en fait environ 4 boucles à la fois (pour un gain de performance x4). Ce gain dépendra de l'architecture de l'unité centrale. L'architecture est susceptible d'être une grande partie du gain, avec les CPU de prochaine génération poussant les gains encore plus loin.
Le vrai problème avec la récursion est que notre matériel est basé sur VonNeumann (variante réalisable de la machine de Turing), et non sur des machines Lisp, bien qu'il existe quelques matériels Lisp spécialisés, vous ne trouverez aucun ordinateur de bureau avec :)
L'utilisation de la récursion présente de nombreux avantages et inconvénients. La simplicité du code est sans aucun doute le plus grand avantage, qui se traduit également par une meilleure maintenabilité du code et une réduction des bogues.
Le plus grand danger de la récursion réside dans les cas limites où l'algorithme devient incontrôlable et dépasse la limite de la pile de fonctions. Certains langages, dont le langage ABL de Progress, ont un paramètre pour le niveau le plus élevé d'appels imbriqués autorisés. Il s'agit généralement d'un niveau bas et l'ajout de la récursion au mélange peut amener une application à dépasser cette limite.
En bref, la récursion doit toujours être implémentée avec des cas de terminaison serrés, sinon elle peut être très difficile à déboguer (à cause de l'imprévisibilité) et peut causer de sérieux problèmes dans le code de production.
En ce qui concerne les problèmes de mémoire et de vitesse, à moins qu'il ne s'agisse d'une méthode courte (en termes de temps) appelée de nombreuses fois, les performances n'ont pas vraiment d'importance.
Exemple : Si vous utilisez la récursion pour analyser tous les fichiers et dossiers d'un disque dur, l'impact de la récursion sur les performances est minuscule par rapport au temps nécessaire pour atteindre le disque dur et saisir les informations du système de fichiers. Dans ce cas, la récursion est probablement préférable au traitement itératif.
Un autre exemple : Si vous parcourez les nœuds d'une structure arborescente, un processus itératif peut être plus bénéfique car nous n'impliquons pas autant la pile de fonctions, ce qui signifie que nous sollicitons moins de mémoire et que nous laissons probablement le matériel utiliser davantage de cache. Voir la réponse de Robert Gould pour plus de détails.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
