Sobrecarga de recursión: ¿qué tan serio es?

Question

Duplicar posible:
Is recursion ever faster than looping?

que se formó primero en programar en C serio, hace unos 15 años. Mi empleador quería un código altamente optimizado para tareas computacionalmente difíciles. Recuerdo que en más de una ocasión me aconsejaron que reescribiera las repeticiones como bucles, incluso al costo de la legibilidad, para evitar la "sobrecarga por recursión". Según entendí entonces, la sobrecarga de recursión fue el esfuerzo extra requerido para insertar datos en una pila y luego sobresalirlos.

Ahora código en C, Python, Perl, y a veces Java, y me pregunto algunas veces sobre las recurrencias. ¿Todavía hay algo que ganar reescribiéndolos? ¿Qué pasa si son repeticiones de cola? ¿Los compiladores modernos han hecho que todos estos problemas sean discutibles? ¿Son estas preocupaciones irrelevantes para los idiomas interpretados?

Answer 1

La recursividad puede provocar una sobrecarga significativa si el núcleo de la función recursiva es menos costoso desde el punto de vista informático que el código de entrada/salida de función y el costo de la llamada en sí. La mejor manera de averiguarlo es simplemente perfilar dos versiones del código, una recursiva y otra no.

Dicho esto, si su idea de evitar la recursividad es hacer usted mismo una estructura en forma de pila, tenga cuidado, puede no ser necesariamente más rápido que el enfoque recursivo más directo. De nuevo, perfilar es tu amigo.

Finalmente, recuerde que el tiempo del programador es más caro que el tiempo de la CPU. Antes de micro-optimizar su código, realmente es una buena idea medir para ver si realmente será un problema.

Answer 2

No creo que ninguno de los idiomas que mencionó requiera que la plataforma/compilador implemente tail call elimination. Puede encontrar los idiomas que do 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 convertido en órdenes de magnitudes más rápidas que hace 15 años, por lo que ahora es mucho más raro que tengas que preocuparte por las micro optimizaciones. Un programa que hace 15 años podría haber requerido una cuidadosa optimización manual en el ensamblador para obtener un rendimiento decente podría funcionar increíblemente rápido en una computadora moderna, incluso si está escrito en un lenguaje de nivel superior como Java. Eso no quiere decir que el rendimiento ya no sea un problema, pero debe concentrarse en elegir el algoritmo correcto y en escribir código legible. Solo haga micro-optimizaciones después de haber medido el rendimiento y puede ver que el código en cuestión es el cuello de botella.

Una cosa que do tiene que preocuparse, aunque se está desbordando la pila. Si hay algún riesgo de que eso suceda, podría valer la pena reescribir una función recursiva de forma iterativa.

Answer 3

Es serio. La mayoría de los lenguajes que codigo tienen un costo real para las llamadas a función (los compiladores para ellos generalmente pueden hacer recursividad de cola también, 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 utilizar la recursividad solo en los casos en que sé que hay un límite en la profundidad a la que puede llegar.

Por ejemplo, sé que una búsqueda de árbol binario equilibrado solo tendrá cincuenta niveles de profundidad para un cuatrillón de entradas. Yo no, sin embargo, utilizar:

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 4

El problema persiste. La recursión requiere mucho espacio de pila, ya que cada vez que un método se llama a sí mismo, se genera un puntero a él y sus variables locales se generan nuevamente. El número de llamadas de función realizadas durante la recursión hace que el uso de la memoria O (n); comparado con O (1) de una función no recursiva como bucles.

Answer 5

La gente dice muchas cosas tontas sobre el rendimiento.

1. Si necesidad recursividad, le gusta hacer a pie de árbol primero en profundidad, entonces que lo necesite, a fin de utilizarlo.

2. Antes de preocuparse por el rendimiento de cualquier cosa, descubra si tiene un problema y donde está.
   Los problemas de rendimiento son como estafadores y embusteros: se especializan en estar donde menos te lo esperas, por lo que si estás preocupado por algo específico como la recursividad, es casi seguro que te preocupes por algo incorrecto.

En mi opinión, la mejor manera de encontrar problemas de rendimiento es mediante la toma de muestras pila en el tiempo del reloj de pared y examining the samples to see what the program is doing, no sólo por conseguir mediciones y preguntándose lo que significan.

Dicho esto, si encuentra un 10% o más de tiempo recurriendo a una llamada recursiva, y no sucede mucho más dentro de la rutina recursiva, y puede recorrerlo, probablemente sea útil ponerlo en bucle.