performance - usar - ¿Recursión o iteración?
recursividad en programacion (28)
Al usar la recursividad, estás incurriendo en el costo de una llamada de función con cada "iteración", mientras que con un bucle, lo único que pagas normalmente es un incremento / decremento. Entonces, si el código para el bucle no es mucho más complicado que el código para la solución recursiva, el bucle generalmente será superior a la recursión.
¿Hay un impacto en el rendimiento si usamos bucle en lugar de recursión o viceversa en algoritmos donde ambos pueden servir para el mismo propósito? Ej .: verificar si la cadena dada es palíndromo. He visto a muchos programadores usar la recursión como un medio para presumir cuando un algoritmo de iteración simple puede ajustarse a la cuenta. ¿El compilador juega un papel vital en decidir qué usar?
Comparar la recursión con la iteración es como comparar un destornillador Phillips con un destornillador plano. En su mayor parte, usted podría quitar cualquier tornillo de cabeza phillips con una cabeza plana, pero sería más fácil si usara el destornillador diseñado para ese tornillo, ¿no?
Algunos algoritmos simplemente se prestan a la recursión debido a la forma en que están diseñados (secuencias de Fibonacci, atravesando una estructura similar a un árbol, etc.). La recursión hace que el algoritmo sea más breve y fácil de entender (por lo tanto, se puede compartir y reutilizar).
Además, algunos algoritmos recursivos utilizan la "Evaluación perezosa", que los hace más eficientes que sus hermanos iterativos. Esto significa que solo hacen los cálculos costosos en el momento en que son necesarios en lugar de cada vez que se ejecuta el bucle.
Eso debería ser suficiente para que comiences. Voy a desenterrar algunos artículos y ejemplos para ti también.
Enlace 1: Haskel vs PHP (Recursión vs Iteración)
Aquí hay un ejemplo donde el programador tuvo que procesar un gran conjunto de datos usando PHP. Muestra lo fácil que habría sido tratar con Haskel utilizando la recursión, pero dado que PHP no tenía una manera fácil de lograr el mismo método, se vio obligado a usar la iteración para obtener el resultado.
http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html
Enlace 2: Dominar la recursión
La mayor parte de la mala reputación de la recursión proviene de los altos costos y la ineficiencia de los idiomas imperativos. El autor de este artículo habla sobre cómo optimizar los algoritmos recursivos para hacerlos más rápidos y eficientes. También explica cómo convertir un bucle tradicional en una función recursiva y los beneficios de usar la recursión final. Sus palabras de cierre realmente resumieron algunos de mis puntos clave, creo:
"la programación recursiva le brinda al programador una mejor manera de organizar el código de una manera que sea tanto mantenible como lógicamente consistente".
http://www.ibm.com/developerworks/linux/library/l-recurs/index.html
Enlace 3: ¿La recursión es más rápida que el bucle? (Responder)
Aquí hay un enlace a una respuesta para una pregunta de que es similar a la suya. El autor señala que muchos de los puntos de referencia asociados con la repetición o el bucle son muy específicos del lenguaje. Los lenguajes imperativos suelen ser más rápidos usando un bucle y más lentos con recursión y viceversa para lenguajes funcionales. Supongo que el punto principal de este enlace es que es muy difícil responder a la pregunta en un sentido agnóstico del lenguaje / situación.
Creo que la recursión de la cola en Java no está optimizada actualmente. Los detalles se esparcen a lo largo de this discusión sobre LtU y los enlaces asociados. Puede ser una característica en la próxima versión 7, pero aparentemente presenta ciertas dificultades cuando se combina con la Inspección de pila, ya que faltan algunos marcos. Stack Inspection se ha utilizado para implementar su modelo de seguridad detallado desde Java 2.
Debe tener en cuenta que si utiliza una recursión demasiado profunda, se encontrará con Desbordamiento de pila, dependiendo del tamaño de pila permitido. Para evitar esto, asegúrese de proporcionar algún caso base que finalice su recursión.
Depende del idioma. En Java debes usar loops. Los lenguajes funcionales optimizan la recursividad.
El desbordamiento de la pila solo se producirá si está programando en un lenguaje que no tiene administración de memoria integrada ... De lo contrario, asegúrese de tener algo en su función (o una llamada de función, STDLbs, etc.). Sin la recursión, simplemente no sería posible tener cosas como ... Google o SQL, o en cualquier lugar en el que se deban clasificar de forma eficiente estructuras de datos grandes (clases) o bases de datos.
La recursión es el camino a seguir si desea recorrer los archivos, bastante seguro de que así es como ''encontrar * | ? grep * ''funciona. Un poco de recursión dual, especialmente con la tubería (pero no hagas un montón de syscalls como a muchos les gusta hacer si es algo que vas a poner para que otros usen).
Los lenguajes de nivel superior e incluso clang / cpp pueden implementarlo de la misma manera en segundo plano.
En C ++, si la función recursiva es una plantilla, entonces el compilador tiene más posibilidades de optimizarla, ya que todas las deducciones de tipo y las instancias de función se producirán en tiempo de compilación. Los compiladores modernos también pueden alinear la función si es posible. Entonces, si uno usa -O2 optimización como -O2 o -O2 en g++ , entonces las recursiones pueden tener la oportunidad de ser más rápidas que las iteraciones. En los códigos iterativos, el compilador tiene menos posibilidades de optimizarlo, ya que se encuentra en un estado más o menos óptimo (si está escrito lo suficientemente bien).
En mi caso, estaba tratando de implementar la exponenciación matricial mediante el uso del cuadrado utilizando objetos de matriz de Armadillo, de forma recursiva e iterativa. El algoritmo se puede encontrar aquí ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring . Mis funciones estaban basadas en plantillas y he calculado 1,000,000 matrices 12x12 elevadas a la potencia 10 . Obtuve el siguiente resultado:
iterative + optimisation flag -O3 -> 2.79.. sec
recursive + optimisation flag -O3 -> 1.32.. sec
iterative + No-optimisation flag -> 2.83.. sec
recursive + No-optimisation flag -> 4.15.. sec
Estos resultados se han obtenido utilizando gcc-4.8 con el indicador c ++ 11 ( -std=c++11 ) y Armadillo 6.1 con Intel mkl. El compilador de Intel también muestra resultados similares.
En muchos casos, la recursión es más rápida debido al almacenamiento en caché, lo que mejora el rendimiento. Por ejemplo, aquí hay una versión iterativa de la ordenación de fusión usando la rutina de fusión tradicional. Se ejecutará más lento que la implementación recursiva debido al almacenamiento en caché de los rendimientos mejorados.
Implementación iterativa
public static void sort(Comparable[] a)
{
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
Implementación recursiva
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);
}
PD: esto es lo que dijo el profesor Kevin Wayne (Universidad de Princeton) en el curso sobre algoritmos presentado en Coursera.
Es posible que la recursión sea más costosa, dependiendo de si la función recursiva es cola recursiva (la última línea es llamada recursiva). La recursión de cola debe ser reconocida por el compilador y optimizada para su contraparte iterativa (manteniendo la implementación clara y concisa que tiene en su código).
Escribiría el algoritmo de la manera que tenga más sentido y sea el más claro para el pobre tonto (ya sea usted mismo o alguien más) que debe mantener el código en unos pocos meses o años. Si se encuentra con problemas de rendimiento, perfile su código y, a continuación, solo busque la optimización moviéndose hacia una implementación iterativa. Es posible que desee mirar en la memoization y la programación dinámica .
Hay muchos casos en los que proporciona una solución mucho más elegante que el método iterativo, el ejemplo común es el recorrido de un árbol binario, por lo que no es necesariamente más difícil de mantener. En general, las versiones iterativas suelen ser un poco más rápidas (y durante la optimización pueden reemplazar una versión recursiva), pero las versiones recursivas son más sencillas de comprender e implementar correctamente.
La recursión es más costosa en la memoria, ya que cada llamada recursiva generalmente requiere que la dirección de la memoria se inserte en la pila, para que luego el programa pueda volver a ese punto.
Sin embargo, hay muchos casos en los que la recursión es mucho más natural y legible que los bucles, como cuando se trabaja con árboles. En estos casos recomendaría apegarse a la recursión.
La recursión es más simple (y, por lo tanto, más fundamental) que cualquier definición posible de una iteración. Puede definir un sistema completo de Turing con solo un par de combinadores (sí, incluso una recursión en sí misma es una noción derivada de dicho sistema). Lambda cálculo Lambda es un sistema fundamental igualmente poderoso, con funciones recursivas. Pero si desea definir una iteración correctamente, necesitaría mucho más primitivos para empezar.
En cuanto al código, no, el código recursivo es, de hecho, mucho más fácil de entender y mantener que uno puramente iterativo, ya que la mayoría de las estructuras de datos son recursivas. Por supuesto, para hacerlo bien, se necesita un lenguaje con soporte para funciones y cierres de alto orden, al menos, para obtener todos los combinadores e iteradores estándar de manera ordenada. En C ++, por supuesto, las soluciones recursivas complicadas pueden parecer un poco feas, a menos que seas un usuario incondicional de FC++ y otros.
La recursión es mejor que la iteración de problemas que se pueden dividir en varias piezas más pequeñas.
Por ejemplo, para hacer un algoritmo de Fibonnaci recursivo, se descompone fib (n) en fib (n-1) y fib (n-2) y se calculan ambas partes. La iteración solo le permite repetir una sola función una y otra vez.
Sin embargo, Fibonacci es en realidad un ejemplo roto y creo que la iteración es en realidad más eficiente. Observe que fib (n) = fib (n-1) + fib (n-2) y fib (n-1) = fib (n-2) + fib (n-3). fib (n-1) se calcula dos veces!
Un mejor ejemplo es un algoritmo recursivo para un árbol. El problema de analizar el nodo principal se puede dividir en múltiples problemas más pequeños al analizar cada nodo secundario. A diferencia del ejemplo de Fibonacci, los problemas más pequeños son independientes entre sí.
Así que sí, la recursión es mejor que la iteración de problemas que pueden dividirse en múltiples problemas más pequeños, independientes e similares.
La recursión es muy útil en algunas situaciones. Por ejemplo considera el código para encontrar el factorial.
int factorial ( int input )
{
int x, fact = 1;
for ( x = input; x > 1; x--)
fact *= x;
return fact;
}
Ahora considérelo usando la función recursiva
int factorial ( int input )
{
if (input == 0)
{
return 1;
}
return input * factorial(input - 1);
}
Al observar estos dos, podemos ver que la recursión es fácil de entender. Pero si no se usa con cuidado, también puede ser propenso a muchos errores. Supongamos que si perdemos if (input == 0) , entonces el código se ejecutará por algún tiempo y termina con un desbordamiento de pila.
La recursión tiene la desventaja de que el algoritmo que escribe utilizando la recursión tiene una complejidad de espacio O (n). Si bien el enfoque iterativo tiene una complejidad de espacio de O (1). Esta es la ventaja de usar la iteración sobre la recursión. Entonces, ¿por qué usamos la recursión?
Vea abajo.
A veces es más fácil escribir un algoritmo usando la recursión, mientras que es un poco más difícil escribir el mismo algoritmo usando la iteración. En este caso, si opta por seguir el enfoque de iteración, tendrá que manejar la pila usted mismo.
La recursión y la iteración dependen de la lógica de negocios que desea implementar, aunque en la mayoría de los casos se puede usar de manera indistinta. La mayoría de los desarrolladores optan por la recursión porque es más fácil de entender.
Los bucles pueden lograr una ganancia de rendimiento para su programa. La recursión puede lograr una ganancia de rendimiento para su programador. ¡Elige cuál es más importante en tu situación!
Mike tiene razón. El compilador de Java o la JVM no optimizan la recursión de la cola. Siempre obtendrás un desbordamiento de pila con algo como esto:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
Pensaría que en la recursión (sin cola) habría un impacto de rendimiento para asignar una nueva pila, etc. cada vez que se llama a la función (depende del idioma, por supuesto).
Por lo general, uno esperaría que la penalización de rendimiento se encuentre en la otra dirección. Las llamadas recursivas pueden conducir a la construcción de marcos de pila adicionales; la pena para esto varía. Además, en algunos lenguajes como Python (más correctamente, en algunas implementaciones de algunos lenguajes ...), puede ejecutar límites de pila con bastante facilidad para las tareas que puede especificar de forma recursiva, como encontrar el valor máximo en una estructura de datos de árbol. En estos casos, realmente quieres seguir con los bucles.
Escribir buenas funciones recursivas puede reducir un poco la penalización del rendimiento, suponiendo que tenga un compilador que optimice las recursiones de la cola, etc. (También compruebe que la función realmente sea recursiva de la cola, es una de esas cosas en las que muchas personas cometen errores) en.)
Aparte de los casos "de vanguardia" (computación de alto rendimiento, profundidad de recursión muy grande, etc.), es preferible adoptar el enfoque que exprese más claramente su intención, esté bien diseñado y se pueda mantener. Optimizar solo después de identificar una necesidad.
Que yo sepa, Perl no optimiza las llamadas recursivas de cola, pero puede falsificarlas.
sub f{
my($l,$r) = @_;
if( $l >= $r ){
return $l;
} else {
# return f( $l+1, $r );
@_ = ( $l+1, $r );
goto &f;
}
}
Cuando se llama por primera vez, asignará espacio en la pila. Luego cambiará sus argumentos y reiniciará la subrutina, sin agregar nada más a la pila. Por lo tanto, fingirá que nunca se llamó a sí mismo, convirtiéndolo en un proceso iterativo.
Tenga en cuenta que no hay " my @_; " o " local @_; ", si lo hiciera ya no funcionaría.
Recursion ¿Por dónde empiezo, wiki te dirá "es el proceso de repetir elementos de manera similar"
De vuelta en el día cuando estaba haciendo C, la recursión de C ++ era un envío de Dios, cosas como "Recursión de cola". También encontrarás que muchos algoritmos de clasificación usan la recursión. Ejemplo de clasificación rápida: http://alienryderflex.com/quicksort/
La recursión es como cualquier otro algoritmo útil para un problema específico. Tal vez no encuentre un uso inmediato o con frecuencia, pero habrá un problema que le alegrará que esté disponible.
Si las iteraciones son atómicas y los órdenes de magnitud son más caros que empujar un nuevo marco de pila y crear un nuevo hilo y tiene múltiples núcleos y su entorno de tiempo de ejecución puede usarlos todos, entonces un enfoque recursivo podría producir un gran aumento de rendimiento cuando se combina con multihilo Si el número promedio de iteraciones no es predecible, entonces sería una buena idea usar un grupo de subprocesos que controlará la asignación de subprocesos y evitará que su proceso cree demasiados subprocesos y acapare al sistema.
Por ejemplo, en algunos idiomas hay implementaciones de ordenamiento de fusión multihebra recursivas.
Pero, de nuevo, el subprocesamiento múltiple se puede usar con bucles en lugar de recursión, por lo que la combinación funcionará dependiendo de más factores, incluido el sistema operativo y su mecanismo de asignación de subprocesos.
Si solo estás iterando sobre una lista, claro, itera lejos.
Un par de otras respuestas han mencionado (primero en profundidad) el recorrido del árbol. Realmente es un gran ejemplo, porque es algo muy común que se hace con una estructura de datos muy común. La recursión es extremadamente intuitiva para este problema.
Echa un vistazo a los métodos de "búsqueda" aquí: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html
Su rendimiento se deteriora al usar la recursión porque llamar a un método, en cualquier idioma, implica mucha preparación: el código de llamada publica una dirección de retorno, parámetros de llamada, otra información de contexto, como los registros del procesador, pueden guardarse en algún lugar, y en el momento de la devolución el método llamado publica un valor de retorno que luego es recuperado por la persona que llama, y se restaurará cualquier información de contexto que se haya guardado previamente. la diferencia de rendimiento entre un enfoque iterativo y recursivo reside en el tiempo que llevan estas operaciones.
Desde el punto de vista de la implementación, realmente empiezas a notar la diferencia cuando el tiempo que lleva manejar el contexto de la llamada es comparable al tiempo que tarda el método en ejecutarse. Si su método recursivo tarda más tiempo en ejecutarse, entonces la parte de administración del contexto de llamada, vaya de forma recursiva, ya que el código generalmente es más legible y fácil de entender y no notará la pérdida de rendimiento. De lo contrario vaya iterativo por razones de eficiencia.
Usando solo Chrome 45.0.2454.85 m, la recursión parece ser una buena cantidad más rápida.
Aquí está el código:
(function recursionVsForLoop(global) {
"use strict";
// Perf test
function perfTest() {}
perfTest.prototype.do = function(ns, fn) {
console.time(ns);
fn();
console.timeEnd(ns);
};
// Recursion method
(function recur() {
var count = 0;
global.recurFn = function recurFn(fn, cycles) {
fn();
count = count + 1;
if (count !== cycles) recurFn(fn, cycles);
};
})();
// Looped method
function loopFn(fn, cycles) {
for (var i = 0; i < cycles; i++) {
fn();
}
}
// Tests
var curTest = new perfTest(),
testsToRun = 100;
curTest.do(''recursion'', function() {
recurFn(function() {
console.log(''a recur run.'');
}, testsToRun);
});
curTest.do(''loop'', function() {
loopFn(function() {
console.log(''a loop run.'');
}, testsToRun);
});
})(window);
RESULTADOS
// 100 carreras usando standard para loop
100x para la ejecución de bucle. Tiempo para completar: 7.683ms
// 100 ejecuciones utilizando un enfoque recursivo funcional con recursión de cola
Recursión 100x ejecutada. Tiempo para completar: 4.841ms
En la captura de pantalla a continuación, la recursión gana nuevamente por un margen mayor cuando se ejecuta a 300 ciclos por prueba
Voy a responder a su pregunta diseñando una estructura de datos de Haskell por "inducción", que es una especie de "doble" a la recursión. Y luego mostraré cómo esta dualidad conduce a cosas buenas.
Introducimos un tipo para un árbol simple:
data Tree a = Branch (Tree a) (Tree a)
| Leaf a
deriving (Eq)
Podemos leer esta definición diciendo "Un árbol es una Rama (que contiene dos árboles) o es una hoja (que contiene un valor de datos)". Así que la hoja es una especie de estuche mínimo. Si un árbol no es una hoja, entonces debe ser un árbol compuesto que contiene dos árboles. Estos son los únicos casos.
Hagamos un árbol:
example :: Tree Int
example = Branch (Leaf 1)
(Branch (Leaf 2)
(Leaf 3))
Ahora, supongamos que queremos agregar 1 a cada valor en el árbol. Podemos hacerlo llamando al
addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a) = Leaf (a + 1)
Primero, note que esto es de hecho una definición recursiva. Toma los constructores de datos Branch y Leaf como casos (y dado que Leaf es mínimo y estos son los únicos casos posibles), estamos seguros de que la función terminará.
¿Qué se necesitaría para escribir addOne en un estilo iterativo? ¿Qué aspecto tendrá un bucle en un número arbitrario de ramas?
Además, este tipo de recursión a menudo se puede eliminar, en términos de un "funtor". Podemos hacer árboles en funciones definiendo:
instance Functor Tree where fmap f (Leaf a) = Leaf (f a)
fmap f (Branch a b) = Branch (fmap f a) (fmap f b)
y definiendo:
addOne'' = fmap (+1)
Podemos factorizar otros esquemas de recursión, como el catamorfismo (o pliegue) para un tipo de datos algebraico. Usando un catamorfismo, podemos escribir:
addOne'''' = cata go where
go (Leaf a) = Leaf (a + 1)
go (Branch a b) = Branch a b
depende de la "profundidad de recursion". depende de cuánto influirá la sobrecarga de llamada a la función en el tiempo total de ejecución.
Por ejemplo, calcular el factorial clásico de manera recursiva es muy ineficiente debido a: - el riesgo de desbordamiento de datos - el riesgo de desbordamiento de pila - la sobrecarga de llamadas de función ocupa el 80% del tiempo de ejecución
mientras se desarrolla un algoritmo mínimo-máximo para el análisis de posición en el juego de ajedrez que analizará los movimientos subsiguientes de N, se puede implementar en forma recursiva sobre la "profundidad de análisis" (como lo estoy haciendo ^ _ ^)