Recientemente he leído algunos artículos (por ejemplo, http://dailyjs.com/2012/09/14/functional-programming/ ) sobre los aspectos funcionales de Javascript y la relación entre Scheme y Javascript (este último fue influenciado por el primero, que es un lenguaje funcional, mientras que los aspectos OO se heredan de Self, que es un lenguaje basado en prototipos).
Sin embargo, mi pregunta es más específica: me preguntaba si hay métricas sobre el rendimiento de la recursión frente a la iteración en Javascript.
Sé que en algunos idiomas (donde la iteración de diseño funciona mejor) la diferencia es mínima porque el intérprete / compilador convierte la recursión en iteración, sin embargo, supongo que probablemente este no sea el caso de Javascript ya que es, al menos parcialmente, funcional idioma.
Respuestas:
JavaScript no realiza la optimización de recursión de cola , por lo que si su recursión es demasiado profunda, puede obtener un desbordamiento de la pila de llamadas. La iteración no tiene tales problemas. Si cree que va a recurrir demasiado y realmente necesita recurrencia (por ejemplo, para rellenar con inundación), reemplace la recurrencia con su propia pila.
El rendimiento de recursión es probablemente peor que el rendimiento de la iteración, porque las llamadas a funciones y los retornos requieren la preservación y restauración del estado, mientras que la iteración simplemente salta a otro punto en una función.
fuente
var stack = []; var factorial = function(n) { if(n === 0) { return 1 } else { stack[n-1] = n * factorial(n - 1); return stack[n-1]; } }elseen esa función conelse if (stack[n-1]) { return stack[n-1]; } elsey tiene memoria . Quien escribió ese código factorial tuvo una implementación incompleta (y probablemente debería haberlo usado enstack[n]todas partes en lugar destack[n-1]).Actualización : desde ES2015, JavaScript tiene TCO , por lo que parte del argumento a continuación ya no es válido.
Aunque Javascript no tiene una optimización de llamadas de cola, la recursión es a menudo la mejor manera de hacerlo. Y sinceramente, excepto en casos extremos, no obtendrá desbordamientos de la pila de llamadas.
El rendimiento es algo a tener en cuenta, pero también la optimización prematura. Si crees que la recursividad es más elegante que la iteración, entonces hazlo. Si resulta que este es su cuello de botella (que puede que nunca lo sea), puede reemplazarlo con alguna iteración fea. Pero la mayoría de las veces, el cuello de botella se encuentra en las manipulaciones DOM o, más en general, en las E / S, no en el código en sí.
La recursión siempre es más elegante 1 .
1 : Opinión personal.
fuente
Tenía bastante curiosidad sobre este rendimiento en JavaScript también, así que hice algunos experimentos (aunque en una versión anterior del nodo). Escribí una calculadora factorial de forma recursiva frente a iteraciones y la ejecuté varias veces localmente. El resultado parecía bastante sesgado hacia la recursión con un impuesto (esperado).
Código: https://github.com/j03m/trickyQuestions/blob/master/factorial.js
fuente
"use strict";y ver si hace la diferencia. (Producirájumps en lugar de la secuencia de llamada estándar)Según lo solicitado por el OP , voy a participar (sin hacer el ridículo, con suerte: P)
Creo que todos estamos de acuerdo en que la recursividad es solo una forma más elegante de codificación. Si se hace bien, puede hacer que el código sea más fácil de mantener, lo cual es IMHO tan importante (si no más) que reducir 0.0001ms.
En lo que respecta al argumento de que JS no realiza la optimización de llamadas de cola: eso ya no es del todo cierto, el uso del modo estricto de ECMA5 habilita el TCO. Era algo de lo que no estaba muy contento hace un tiempo, pero al menos ahora sé por qué
arguments.calleearroja errores en modo estricto. Sé que el enlace de arriba enlaza con un informe de error, pero el error está configurado en WONTFIX. Además, viene el TCO estándar: ECMA6 (diciembre de 2013).Instintivamente, y atendiendo a la naturaleza funcional de JS, diría que la recursión es el estilo de codificación más eficiente el 99.99% del tiempo. Sin embargo, Florian Margaine tiene razón cuando dice que es probable que se encuentre el cuello de botella en otro lugar. Si está manipulando el DOM, probablemente esté mejor enfocado en escribir su código lo más fácil de mantener posible. La API DOM es lo que es: lenta.
Creo que es casi imposible ofrecer una respuesta definitiva sobre cuál es la opción más rápida. Últimamente, muchos jspref que he visto muestran que el motor V8 de Chrome es ridículamente rápido en algunas tareas, que funcionan 4 veces más lento en SpiderMonkey de FF y viceversa. Los motores JS modernos tienen todo tipo de trucos bajo la manga para optimizar su código. No soy un experto, pero siento que V8, por ejemplo, está altamente optimizado para cierres (y recursividad), mientras que el motor JScript de MS no lo está. SpiderMonkey a menudo funciona mejor cuando el DOM está involucrado ...
En resumen: diría que la técnica que tendrá más rendimiento es, como siempre en JS, casi imposible de predecir.
fuente
Sin el modo estricto, el rendimiento de iteración suele ser ligeramente más rápido que la recursividad ( además de hacer que el JIT haga más trabajo ). La optimización de recursión de cola esencialmente elimina cualquier diferencia notable porque convierte toda la secuencia de llamadas en un salto.
Ejemplo: Jsperf
Sugeriría preocuparse mucho más por la claridad y simplicidad del código cuando se trata de elegir entre recursividad e iteración.
fuente