language agnostic - Recursión o iteración?
language-agnostic optimization (14)
¿Alguien sabe si hay alguna buena razón para no utilizar la recursión en los idiomas como C #? ¿Es más caro que la iteración?
Sí, porque C # no admite la recursividad de cola . Al usar la recursividad para la iteración simple a través de grandes colecciones, puede obtener fácilmente una StackOverflowException y bloquear su aplicación si recurre demasiado profundamente.
Me encanta la recursividad. Creo que simplifica mucho las cosas. Otro puede estar en desacuerdo; Creo que también hace que el código sea mucho más fácil de leer. Sin embargo, he notado que la recursividad no se usa tanto en idiomas como C #, ya que están en LISP (que por cierto es mi idioma favorito debido a la recursión).
¿Alguien sabe si hay alguna buena razón para no utilizar la recursión en los idiomas como C #? ¿Es más caro que la iteración?
¿Son más caros que las iteraciones?
Sí lo son. La recursión requiere la creación de un nuevo marco de pila junto con una llamada y devolución, mientras que la iteración generalmente solo requiere una comparación y una rama que la hace sustancialmente más rápida; sin embargo, los compiladores pueden realizar la optimización de llamadas de cola en ciertas llamadas recursivas (llamadas de cola) que les permiten reutilizar el marco de pila haciendo que la llamada recursiva sea mucho menos costosa y convirtiéndola en iteración. El esquema realmente requiere que los compiladores de esquemas implementen la optimización de la llamada de cola.
¿Son más caros que las iteraciones?
Sí lo son. Muchas variantes de Lisp respaldan la idea de una "optimización de llamada final" que permite que muchos usos de una llamada a función recursiva se conviertan en iterativos (esto simplifica un poco). Si no se admite la llamada final, una llamada de función recursiva usará progresivamente más memoria en la pila.
Cuando se trata de una estructura de datos intrínsecamente lineal, como la lista o el vector, una de las razones para preferir el constructo iterativo sobre la recursión es que transmite mejor la intención de su código. Con frecuencia requiere más esfuerzo para que el lector discierna la estructura de su programa cuando la recursión se usa indiscriminadamente cuando la iteración es suficiente.
El compilador y la arquitectura de las CPU modernas pueden hacer muchas optimizaciones con iteración que no pueden hacer con la recursión. Por ejemplo, la capacidad del procesador para realizar cálculos optimistas. Cuando el procesador encuentra un espacio de iteración, sabe cuánto tiempo llevará. Desde el principio, no hay necesidad real de verificar cada vez antes de comenzar el siguiente ciclo. Entonces, canalizan las operaciones. Como la mayoría de las CPU pueden hacer varias operaciones al mismo tiempo (a través de la canalización), puede resolver el espacio de iteración en menos tiempo que la recursión. Esto es incluso con la optimización de la cola porque la CPU está procesando aproximadamente 4 bucles a la vez (para una ganancia de rendimiento de x4). Esta ganancia dependerá de la arquitectura de la CPU. Es probable que la arquitectura sea una gran parte de la ganancia, con las CPU de próxima generación impulsando las ganancias incluso más allá.
El verdadero problema con la recursividad es que nuestro hardware está basado en VonNeumann (variante alcanzable de la máquina de Turing), y no en máquinas Lisp, aunque hay algunos hardware Lisp especializado, no encontrará ningún escritorio con él :)
Existen muchos pros y contras para usar la recursión. Definitivamente, la simplicidad del código es la más grande que también se presta a un mejor mantenimiento del código y menos errores.
El mayor peligro para la recursividad son los casos límite en los que el algoritmo se sale de control para romper el límite de la pila de funciones. Algunos lenguajes, el lenguaje ABL de Progress para uno, tiene un parámetro para el nivel más alto de llamadas anidadas permitidas. Estos suelen ser bajos y agregar recursividad a la mezcla podría hacer que una aplicación rompa ese límite.
En resumen, la recursión siempre se debe implementar con casos de terminación estricta, de lo contrario puede ser muy difícil de depurar (debido a la imprevisibilidad) y puede causar problemas graves en el código de producción.
Para las preocupaciones con la memoria y la velocidad, a menos que se trate de un método en sí mismo que es corto (en el tiempo) se llama muchas veces, realmente no importa cuál es el rendimiento.
Ejemplo: si utiliza la recursividad para analizar todos los archivos y carpetas de un disco duro, el impacto en el rendimiento que produce la recursión es minúsculo al tiempo que lleva recorrer el disco duro y obtener la información del sistema de archivos. En este caso, la recursión es probablemente preferible al procesamiento iterativo.
Otro ejemplo: si escanea los nodos de una estructura de árbol, un proceso iterativo puede ser más beneficioso porque no estamos involucrando tanto la pila de funciones, lo que significa que estamos utilizando menos memoria y probablemente dejemos que el hardware use más memoria caché. Ver la respuesta de Robert Gould para más detalles.
La elección no se basa únicamente en el problema a resolver, sino también en el lenguaje utilizado. En los lenguajes estilo C (Java, C #, o lo que sea), mi respuesta instintiva es evitar la recursividad, ya que me parece totalmente ajena (y no puedo pensar recursivamente), por no mencionar el potencial de abuso de pila. Sin embargo, hay algunos problemas para los que casi no tiene sentido usar otra cosa que la recursión: el cruce de árboles es un buen ejemplo. Una solución iterativa es completamente plausible, pero el código sería más grande, más inestable y casi seguramente menos legible.
Sin embargo, un lenguaje más dinámico (como Lisp o Python) hace todo lo posible para que la recursión sea una posibilidad más natural. Mi respuesta personal es buscar primero una solución iterativa, sin importar cuál sea el problema, pero variar el kilometraje hace que una carrera de caballos sea una carrera.
Al final, la mejor opción es simplemente escribirlo. Lo más probable es que lo tires una vez en cualquier caso.
La recursividad es (imposible / mucho más difícil) de paralelizar que la iteración
Las CPUs modernas tienen núcleos múltiples, por lo tanto, la optimización directa con parallel.for (y tales técnicas) se vuelve mucho más difícil si está diseñado para la recursión.
Sin embargo, la paralelización todavía es bastante oscura y relativamente poca gente la usa todavía.
Además, creo que los algos recursivos son más fáciles de diseñar y pensar porque implican un poco menos código y variables al mismo tiempo. Suelo recurrir a la recursividad cuando no hay necesidad de rendimiento.
Los lenguajes funcionales como Lisp y F # pueden implementar muchas funciones recursivas de cola internamente como bucles y pueden evitar la sobrecarga de la pila de una llamada a función. C # no tiene soporte para recursividad de cola, aunque F # sí lo hace.
Scheme es el único dialecto de Lisp que conozco que requiere una optimización de la cola de llamada, y tienden a recurrir mucho a la recursividad. En otros dialectos de Lisp que no requieren esto (como Common Lisp), no veo la recurrencia utilizada más que en cualquier otro idioma.
Si un algoritmo se puede expresar de forma más natural en una forma recursiva, y si la profundidad de la pila es pequeña (en el rango log (N), es decir, típicamente <20), entonces, de cualquier forma, utilice la recursión. (Cualquier ganancia de rendimiento debido a la iteración será un pequeño factor constante).
Si existe algún peligro de que la pila crezca, y si su sistema de lenguaje / compilador / tiempo de ejecución no garantiza la optimización de la cola de llamadas, debe evitar los algoritmos recursivos.
Si un problema puede reducirse a una iteración, entonces iteraré.
Si un problema requiere recursividad (por ejemplo, navegación en árbol), entonces recurse.
Una vez dicho esto, hago las principales aplicaciones de línea de negocios en C #: estoy seguro de que la programación científica tiene un conjunto diferente de requisitos.
Voy a decir que las variables XSLT son de solo lectura una vez creadas. Debido a esto, cosas que se harían con indexado para bucles, como
for(int i=0; i < 3; i++) doIt(i);
en realidad están hechos con recursión. Algo equivalente a
public rediculous(i) {
doIt(i);
if (i < 3) rediculous(i + 1);
}
De hecho, proporcionaría un ejemplo de XSLT aquí, pero todo ese tipeo hace llorar a Baby Jesus.
Creo que las funciones recursivas tienen que colocarse en una pila: cada vez que la función se llama a sí misma, otra copia de esa función va a una pila de funciones, y así sucesivamente. El problema es que, en algún momento, la pila se queda sin espacio para almacenar las funciones, por lo que si los números aumentan, una solución recursiva puede no funcionar. Lo sé porque me mordió el culo: tenía una gran función recursiva para free() toda mi lista vinculada, y luego hice una prueba con la lista enlazada más grande que pude hacer y obtuve un error (creo que fue un segfault - definitivamente debería haber sido un desbordamiento de pila :)).
Las funciones iterativas no tienen estos errores: en el lenguaje de la máquina, se expresan como simples ''jmp o'' je''s, etc., por lo que nunca se quedan sin espacio en la pila de funciones y, de hecho, son más limpios.
Esta es una pregunta totalmente subjetiva, pero si no fuera por el hecho de que la recursividad tiene un límite incorporado en su computadora, diría que es una solución mucho mejor. Algunas soluciones iterativas a problemas simplemente se ven feas, mientras que la solución recursiva se ve mucho más limpia y agradable. Pero tal es la vida.