J'ai lu récemment quelques articles (par exemple http://dailyjs.com/2012/09/14/functional-programming/ ) sur les aspects fonctionnels de Javascript et la relation entre Scheme et Javascript (ce dernier a été influencé par le premier, qui est un langage fonctionnel, tandis que les aspects OO sont hérités de Self qui est un langage basé sur le prototypage).
Cependant ma question est plus précise: je me demandais s'il y avait des métriques sur les performances de la récursion vs l'itération en Javascript.
Je sais que dans certaines langues (où, par conception, l'itération fonctionne mieux), la différence est minime car l'interpréteur / compilateur convertit la récursivité en itération, mais je suppose que ce n'est probablement pas le cas de Javascript car il s'agit, au moins partiellement, d'une fonction la langue.
Réponses:
JavaScript n'effectue pas d'optimisation de la récursivité de queue , donc si votre récursivité est trop profonde, vous pouvez obtenir un débordement de pile d'appels. L'itération n'a pas de tels problèmes. Si vous pensez que vous allez trop récursif et que vous avez vraiment besoin d'une récursivité (par exemple, pour effectuer un remplissage par saturation), remplacez la récursivité par votre propre pile.
Les performances de récursivité sont probablement pires que les performances d'itération, car les appels et les retours de fonctions nécessitent une préservation et une restauration d'état, tandis que l'itération saute simplement à un autre point dans une fonction.
la source
var stack = []; var factorial = function(n) { if(n === 0) { return 1 } else { stack[n-1] = n * factorial(n - 1); return stack[n-1]; } }elsedans cette fonction parelse if (stack[n-1]) { return stack[n-1]; } elseet vous avez la mémorisation . Celui qui a écrit ce code factoriel avait une implémentation incomplète (et aurait probablement dû l'utiliserstack[n]partout au lieu destack[n-1]).Mise à jour : depuis ES2015, JavaScript a un TCO , donc une partie de l'argument ci-dessous ne tient plus.
Bien que Javascript n'ait pas d'optimisation des appels de queue, la récursivité est souvent la meilleure façon de procéder. Et sincèrement, sauf dans les cas extrêmes, vous n'obtiendrez pas de débordements de pile d'appels.
Les performances sont quelque chose à garder à l'esprit, mais aussi une optimisation prématurée. Si vous pensez que la récursivité est plus élégante que l'itération, alors allez-y. S'il s'avère que c'est votre goulot d'étranglement (qui peut ne jamais l'être), vous pouvez le remplacer par une itération laide. Mais la plupart du temps, le goulot d'étranglement réside dans les manipulations DOM ou plus généralement les E / S, pas le code lui-même.
La récursivité est toujours plus élégante 1 .
1 : Opinion personnelle.
la source
J'étais également assez curieux de connaître ces performances en javascript, j'ai donc fait quelques expériences (bien que sur une ancienne version de node). J'ai écrit une calculatrice factorielle récursivement par rapport aux itérations et l'ai exécutée plusieurs fois localement. Le résultat semblait assez fortement biaisé vers une récursivité ayant une taxe (attendue).
Code: https://github.com/j03m/trickyQuestions/blob/master/factorial.js
la source
"use strict";et voir si cela fait une différence. (Il produira desjumps au lieu de la séquence d'appel standard)Selon la demande de l'OP, je participerai (sans me ridiculiser, j'espère: P)
Je pense que nous sommes tous d'accord pour dire que la récursivité est juste une façon plus élégante de coder. Si bien fait, cela peut rendre le code plus maintenable, ce qui est à mon humble avis tout aussi important (sinon plus) que le rasage de 0,0001 ms.
En ce qui concerne l'argument selon lequel JS n'effectue pas l'optimisation des appels de queue: ce n'est plus tout à fait vrai, l' utilisation du mode strict d'ECMA5 permet le TCO. C'était quelque chose dont je n'étais pas trop content il y a quelque temps, mais au moins je sais maintenant pourquoi
arguments.calleejette des erreurs en mode strict. Je connais le lien ci-dessus qui renvoie à un rapport de bogue, mais le bogue est réglé sur WONTFIX. En outre, le TCO standard arrive: ECMA6 (décembre 2013).Instinctivement, et fidèle à la nature fonctionnelle de JS, je dirais que la récursivité est le style de codage le plus efficace 99,99% du temps. Cependant, Florian Margaine a raison de dire qu'il est probable que le goulot d'étranglement se trouve ailleurs. Si vous manipulez le DOM, vous devez probablement vous concentrer sur l'écriture de votre code aussi maintenable que possible. L'API DOM est ce qu'elle est: lente.
Je pense qu'il est presque impossible d'offrir une réponse définitive quant à l'option la plus rapide. Dernièrement, beaucoup de jspref que j'ai vus montrent que le moteur V8 de Chrome est ridiculement rapide pour certaines tâches, qui fonctionnent 4 fois plus lentement sur SpiderMonkey de FF et vice versa. Les moteurs JS modernes ont toutes sortes de trucs dans leurs manches pour optimiser votre code. Je ne suis pas un expert, mais je pense que la V8, par exemple, est hautement optimisée pour les fermetures (et la récursivité), contrairement au moteur JScript de MS. SpiderMonkey fonctionne souvent mieux lorsque le DOM est impliqué ...
En bref: je dirais que la technique qui sera la plus performante est, comme toujours en JS, presque impossible à prévoir.
la source
Sans mode strict, les performances d'itération sont généralement légèrement plus rapides que la récursivité ( en plus de faire travailler le JIT plus ). L'optimisation de la récursivité de queue élimine essentiellement toute différence notable car elle transforme toute la séquence d'appel en un saut.
Exemple: Jsperf
Je suggérerais de m'inquiéter beaucoup plus de la clarté et de la simplicité du code lorsqu'il s'agit de choisir entre la récursivité et l'itération.
la source