Sobrecarga de recursividad: ¿qué tan grave es?[duplicar]

Question

Posible duplicado:
¿La recursividad es alguna vez más rápida que el bucle?

La primera vez que me capacitaron para programar seriamente en C fue hace unos 15 años.Mi empleador quería código altamente optimizado para tareas computacionalmente difíciles.Recuerdo que me aconsejaron más de una vez que reescribiera las recursiones como bucles, incluso con el costoso de la legibilidad, para evitar la "sobrecarga de recursiones". Como lo entendí entonces, la sobrecarga de recursión fue el esfuerzo adicional requerido para empujar los datos a una pila y luego desplegarlo.

Ahora codifico en C, Python, Perl y, a veces, en Java, y a veces me pregunto acerca de las recursiones.¿Todavía se puede ganar algo reescribiéndolos?¿Qué pasa si son recursiones de cola?¿Los compiladores modernos han hecho que todas estas cuestiones sean discutibles?¿Son estas preocupaciones irrelevantes para los idiomas interpretados?

Answer 1

recursión puede conducir a una sobrecarga significativa si el núcleo de la función recursiva es menos costoso computacionalmente que el código de entrada de la función / salida y el costo de la propia llamada. La mejor manera de averiguarlo es simplemente para perfilar dos versiones del código -. Recursiva, y uno no

Dicho esto, si su idea de evitar la repetición es hacer una pila similar a la estructura de ti mismo, ten cuidado - no necesariamente puede ser más rápido que el enfoque recursivo más sencillo. Una vez más, perfilado es su amigo.

Por último, recuerda que el tiempo del programador es más caro que el tiempo de CPU. Antes de micro-optimizar el código, lo que realmente es una buena idea para medir para ver si realmente va a ser un problema.

Answer 2

Es grave. La mayor parte del código de idiomas en la que tienen un coste real para las llamadas de función (los compiladores para ellos por lo general pueden hacer la recursión de cola, así que a veces no es un problema).

Ese costo, y el hecho de que la pila no es un recurso ilimitado, por lo general me hace tienden a utilizar la recursividad sólo para los casos en los que sé que hay un límite en la profundidad que puede ir a.

Por ejemplo, conozco a un árbol binario de búsqueda equilibrado irá solamente cincuenta niveles de profundidad para uno mil billones de entradas. Yo no lo haría, sin embargo, su uso:

def sum1through (n):
    if n == 0 return 0
    return n + sum1through (n-1)

ya que haciendo eso por n de veinte millones no sería saludable para una pila.

Answer 3

todavía existe el problema. Recursividad necesita mucho espacio de pila, ya que cada vez que un método llama a sí mismo, un puntero a ella y sus variables locales se generan de nuevo. El número de llamadas a funciones realizadas durante la recursión hace un O (n) uso de la memoria; en comparación con O (1) de una función no recursiva como bucles.

Answer 4

No creo que ninguno de los idiomas que mencionaste requerir que implementa la plataforma/compilador eliminación de llamadas de cola.Puedes encontrar idiomas que hacer requieren esta optimización; la mayoría de los lenguajes funcionales tienen este requisito.

Sin embargo, otra cosa que debes tener en cuenta es que las computadoras se han vuelto órdenes de magnitud más rápidas que hace 15 años, por lo que es mucho más raro ahora que antes que tengas que preocuparte por las microoptimizaciones.Un programa que hace 15 años podría haber requerido una cuidadosa optimización manual en ensamblador para obtener un rendimiento decente podría ejecutarse increíblemente rápido en una computadora moderna, incluso si está escrito en un lenguaje de nivel superior como Java.Esto no quiere decir que el rendimiento ya no sea un problema, pero debes concentrarte en elegir el algoritmo correcto y al escribir legible código.Realice microoptimizaciones solo después de haber medido el rendimiento y pueda ver que el código en cuestión es el cuello de botella.

una cosa tu hacer Sin embargo, debemos preocuparnos por el desbordamiento de la pila.Si existe algún riesgo de que eso suceda, podría valer la pena reescribir una función recursiva de forma iterativa.

Answer 5

La gente dice muchas cosas tontas sobre el rendimiento.

1. Si necesidad recursión, al igual que hacer a pie de árbol primero en profundidad, entonces se necesita, por lo utilice.

2. Antes de preocuparse por el rendimiento de lo , averiguar si usted tiene un problema y dónde está.
   Los problemas de rendimiento son como los hombres y embaucadores estafadores - se especializan en estar donde menos te lo esperas, así que si usted está preocupado por algo específico, como la recursividad, es casi seguro que preocuparse por lo que no debía

.

En mi opinión, la mejor manera de encontrar problemas de rendimiento es mediante muestreo pila en el tiempo del reloj de pared y examen de las muestras para ver lo que está haciendo el programa , no sólo por conseguir mediciones y preguntándose lo que significan.

Dicho esto, si usted encuentra un 10% o más del tiempo de entrar en una llamada recursiva, y no hay mucho más que sucede dentro de la rutina recursiva, y usted puede bucle, a continuación, un bucle que probablemente ayuda.