La recursividad o la Iteración?
https://stackoverflow.com/questions/72209
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Hay un impacto en el rendimiento si se utiliza un bucle en lugar de la recursividad o viceversa en los algoritmos donde ambos pueden servir para el mismo propósito?Por ejemplo:Comprobar si la cadena es un palíndromo.He visto a muchos programadores mediante la recursividad como un medio para mostrar cuando una simple iteración del algoritmo puede ajustarse a la ley.Hace el compilador juegan un papel vital en la decisión de cuál utilizar?
Solución
Es posible que la recursividad será más caro, dependiendo de si la función recursiva es la cola recursiva (la última línea es llamada recursiva).La recursividad de cola debe ser reconocido por el compilador y optimizado para su iterativo de la contraparte (mientras se mantiene el concisa, clara aplicación que tiene en su código).
Me gustaría escribir el algoritmo en la forma en que tiene más sentido y es la más clara para el pobre imbécil (sea usted mismo o alguien más) que tiene que mantener el código en un par de meses o años.Si llegas a tener problemas de rendimiento, a continuación, el perfil de su código, y entonces y sólo entonces mira en la optimización moviendo a un proceso iterativo de aplicación.Usted puede desear mirar en memoization y programación dinámica.
Otros consejos
Los bucles pueden lograr un aumento del rendimiento en su programa.La recursividad se puede lograr un aumento en el rendimiento de su programador.Elegir qué es más importante en su situación!
La comparación de la recursividad para la iteración es como comparar un destornillador de cabeza phillips para un destornillador de cabeza plana.Para la mayor parte podría quitar ningún tornillo cabeza phillips con una cabeza plana, pero sería más fácil si se utiliza el destornillador diseñado para que el tornillo de la derecha?
Algunos de los algoritmos sólo se prestan a la recursividad por la forma en que están diseñadas (secuencias de Fibonacci, que atraviesa un árbol como la estructura, etc.).La recursividad hace que el algoritmo más concisos y fáciles de entender (por lo tanto, compartible y reutilizables).
También, algunos algoritmos recursivos uso "Evaluación Diferida", que los hace más eficientes que sus iterativo hermanos.Esto significa que sólo las caras de los cálculos en el momento en que se necesitan más cada vez que el bucle se ejecuta.
Eso debería ser suficiente para empezar.Voy a desenterrar algunos artículos y ejemplos para usted también.
Link 1: Haskel vs PHP (Recursión vs Iteración)
Este es un ejemplo donde el programador tenía que procesar un gran conjunto de datos usando PHP.Él muestra lo fácil que hubiera sido para tratar de Haskel el uso de la recursividad, pero desde PHP no tenía manera fácil de lograr el mismo método, se vio obligado a utilizar la iteración para obtener el resultado.
http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html
Enlace 2: Dominar La Recursividad
La mayoría de la recursividad de la mala reputación proviene de los altos costos y la ineficiencia en los lenguajes imperativos.El autor de este artículo habla acerca de cómo optimizar algoritmos recursivos para hacerlas más rápido y más eficiente.Él también va sobre cómo convertir un tradicional bucle en una función recursiva y los beneficios del uso final de la recursión.Sus palabras finales realmente resume algunos de mis puntos clave creo:
"recursiva de programación proporciona al programador una mejor manera de organizar código de una manera que es fácil de mantener y lógicamente consistente."
Link 3: Es la recursividad cada vez más rápido de bucle?(Respuesta)
Aquí hay un enlace a una respuesta a una pregunta de stackoverflow que es similar a la tuya.El autor señala que muchos de los puntos de referencia asociado con recursing o bucle muy lenguaje específico.Lenguajes imperativos son normalmente más rápido utilizando un bucle y más lento con la recursividad y viceversa para los lenguajes funcionales.Supongo que el principal punto a tener a partir de este enlace es que es muy difícil responder a la pregunta en un idioma agnóstico / situación de los ciegos sentido.
La recursividad es más costoso en la memoria, ya que cada llamada recursiva, en general, requiere de una dirección de memoria para ser empujada a la pila para que más tarde el programa podría volver a ese punto.
Aún así, hay muchos casos en los que la recursividad es mucho más natural y legible de los nudos - como cuando se trabaja con árboles.En estos casos yo recomiendo que se pegue a la recursividad.
Normalmente, sería de esperar que el rendimiento de la pena de estar en la otra dirección.Llamadas recursivas pueden conducir a la construcción de extra marcos de pila;la pena por este varía.También, en algunos lenguajes como Python (más correctamente, en algunas implementaciones de algunos idiomas...), que se puede ejecutar en la pila de límites bastante facilidad para las tareas que usted podría especificar de forma recursiva, como encontrar el valor máximo de una estructura de datos en árbol.En estos casos, usted realmente quiere seguir con bucles.
Escribir buenas funciones recursivas pueden reducir el rendimiento de la pena de algo, suponiendo que tiene un compilador que optimiza la cola recursiones, etc.(También doble verificación para asegurarse de que la función es realmente cola recursiva---es una de esas cosas que muchas personas cometen errores en.)
Aparte de "borde" de los casos (computación de alto rendimiento, muy grande profundidad de la recursión, etc.), es preferible adoptar el enfoque que más claramente expresa su intención, está bien diseñada y es fácil de mantener.Optimizar sólo después de la identificación de una necesidad.
La recursividad es mejor que la iteración de los problemas que se pueden dividir en varios, piezas más pequeñas.
Por ejemplo, para hacer un recursiva Fibonnaci algoritmo, se puede romper la fib(n) en el fib(n-1) y fib(n-2) y calcular ambas partes.Iteración sólo se permite la repetición de una sola función una y otra vez.
Sin embargo, Fibonacci es en realidad un roto ejemplo y creo que la iteración es realmente más eficiente.Observe que la 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 padre puede dividirse en varios pequeños problemas de análisis de cada nodo hijo.A diferencia de la de Fibonacci ejemplo, los problemas más pequeños son independientes el uno del otro.
Así que sí, recursividad es mejor que la iteración de los problemas que pueden dividirse en múltiples y pequeños, independientes, problemas similares.
Su desempeño se deteriora cuando el uso de la recursividad, porque una llamada a un método, en cualquier idioma, implica una gran cantidad de la preparación:el código de llamada a los puestos de dirección de retorno, los parámetros de llamada, alguna otra información de contexto, tales como registros del procesador puede ser guardado en algún lugar, y en tiempo de retorno de la llama método registra un valor de retorno que se recuperan por la persona que llama y cualquier información de contexto que se guardó previamente será restaurado.el rendimiento diff entre un proceso iterativo y recursivo enfoque reside en el momento en que estas operaciones tienen.
A partir de una aplicación de punto de vista, realmente empiezas a notar la diferencia cuando el tiempo que se necesita para manejar el contexto de llamada es comparable a la del tiempo que dure el método a ejecutar.Si su método recursivo toma más tiempo para ejecutar, a continuación, el llamado contexto de la gestión de parte, ve la manera recursiva como el código es más legible y fácil de entender, y usted no va a notar la pérdida de rendimiento.De lo contrario, vaya iterativo por razones de eficiencia.
Creo que la cola de la recursividad en java no están optimizados.Los detalles están salpicadas a lo largo de este la discusión sobre la Utp y los enlaces asociados.Es puede ser una característica en la próxima versión 7, pero al parecer presenta ciertas dificultades cuando se combina con la Pila de Inspección desde ciertos marcos sería falta.Pila de Inspección ha sido utilizado para implementar su grano fino modelo de seguridad desde Java 2.
Hay muchos casos donde se da una mucho más elegante solución a través del método iterativo, el ejemplo común de ser recorrido de un árbol binario, por lo que no es necesariamente más difícil de mantener.En general, iterativo versiones son generalmente un poco más rápido (y durante la optimización, bien puede reemplazar una versión recursiva), pero recursiva versiones son más fáciles de comprender y de aplicar correctamente.
La recursividad es muy útil en algunas situaciones.Por ejemplo, considere 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 considere la posibilidad de que mediante el uso de la función recursiva
int factorial ( int input )
{
if (input == 0)
{
return 1;
}
return input * factorial(input - 1);
}
Mediante la observación de estos dos, podemos ver que la recursividad es fácil de entender.Pero si no se usa con cuidado, puede ser mucho más susceptible a errores también.Supongo que si echamos de menos if (input == 0), el código será ejecutado por algún tiempo y termina por lo general con un desbordamiento de pila.
En muchos casos, la recursividad es más rápido debido a la caché, lo que mejora el rendimiento.Por ejemplo, aquí es un proceso iterativo versión de la combinación de ordenar el uso de la tradicional combinación de rutina.Se ejecutará más lento que el recurrente implementación debido a la caché de mejorar los resultados.
Iterativo aplicación
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));
}
Recursivas aplicación
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);
}
PS - esto es lo que fue dicho por el Profesor Kevin Wayne (Universidad de Princeton) en el curso de algoritmos presentados en Coursera.
El uso de la recursividad, estás incurrir en el coste de una llamada a una función con cada uno de los "iteración", mientras que con un bucle, la única cosa que usted paga generalmente es un incremento/decremento.Por lo tanto, si el código del bucle no es mucho más complicado que el código de la solución recursiva, bucle normalmente será superior a la recursividad.
La recursividad e iteración depende de la lógica de negocio que se desea implementar, aunque en la mayoría de los casos se pueden utilizar indistintamente.La mayoría de los desarrolladores de ir a por la recursividad, porque es más fácil de entender.
Depende del lenguaje.En Java debe utilizar bucles.Los lenguajes funcionales optimizar la recursividad.
Si usted está a solo iterar sobre la lista, seguro, repetir de distancia.
Un par de otras respuestas han mencionado (en profundidad) árbol de recorrido.Realmente es un gran ejemplo, porque es algo muy común para hacer a un tipo muy común de estructura de datos.La recursividad es sumamente intuitiva para este problema.
Echa un vistazo al "encontrar" los métodos de aquí:http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html
La recursividad es más simple (y por lo tanto más fundamental) de cualquier posible definición de una iteración.Puede definir una Turing-completo sistema con sólo un par de combinadores (sí, incluso una recursividad en sí es un derivado de la noción de tal sistema). Lambda el cálculo es igual de potente fundamental del sistema, con funciones recursivas.Pero si desea definir una iteración correctamente, se necesita mucho más primitivas a empezar.
Como para el código - no, recursiva, el código es en realidad mucho más fácil de entender y de mantener que una puramente iterativo, ya que la mayoría de las estructuras de datos son recursivos.Por supuesto, con el fin de obtener el derecho de un lenguaje con un soporte para funciones de orden y cierres de, al menos - para obtener los combinadores y los iteradores en una manera clara y ordenada.En C++, por supuesto, complicado recursiva soluciones puede tener un aspecto un poco feo, a menos que seas un usuario hardcore de FC++ y de la misma manera.
Me gustaría pensar en (sin cola) la recursividad no habría un impacto en el rendimiento para la asignación de una nueva pila, etc cada vez que se llama a la función (dependiendo del idioma).
depende de "profundidad de la recursión".depende en gran medida de la función de la sobrecarga de la llamada influirá en el tiempo de ejecución total.
Por ejemplo, calcular el factorial clásico en una manera recursiva es muy ineficiente debido a:- riesgo de los datos desbordante - riesgo de pila desbordante la función de la sobrecarga de la llamada ocupan el 80% del tiempo de ejecución
mientras que el desarrollo de un min-max algoritmo para el análisis de la posición en el juego de ajedrez que analizará posterior N se mueve puede ser aplicado en la recursión sobre el "análisis de la profundidad" (como yo lo hago ^_^)
La recursividad?Por dónde empiezo, wiki y te dirán: "es el proceso de la repetición de elementos en una auto-similar manera"
De vuelta en el día, cuando yo estaba haciendo C, C++ recursividad fue un regalo de dios, cosas como "Cola " recursividad".Usted también encontrará muchos algoritmos de ordenación de uso de la recursividad.Ordenación rápida ejemplo: http://alienryderflex.com/quicksort/
La recursividad es como cualquier otro algoritmo útil para un problema específico.Tal vez usted podría no encontrar un uso inmediato o, a menudo, pero no habrá problema se alegrará de lo que hay disponible.
En C++ si la función recursiva es una plantilla de uno, entonces el compilador tiene más posibilidades de optimizar, que es el tipo de la deducción y la función de los casos se producen en tiempo de compilación.Los compiladores modernos, también en línea de la función, si es posible.Así que si uno utiliza parámetros de optimización como -O3 o -O2 en g++, a continuación, las repeticiones pueden tener la posibilidad de ser más rápido que el de iteraciones.En el proceso iterativo de códigos, el compilador tiene menos oportunidad para optimizar, ya que se encuentra ya en la más o menos en un estado óptimo (si escriben bastante bien).
En mi caso, yo estaba tratando de implementar la matriz de exponenciación elevando al cuadrado el uso de Armadillo matriz de objetos, en tanto recursivo e iterativo manera.El algoritmo se puede encontrar aquí... https://en.wikipedia.org/wiki/Exponentiation_by_squaring.Mis funciones eran de plantilla y he calculado 1,000,000 12x12 matrices elevado a la potencia 10.Tengo 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 han sido obtenidos utilizando gcc-4.8 con c++11 de la bandera (-std=c++11) y el Armadillo 6.1 con Intel mkl.Intel compilador también muestra resultados similares.
Mike es correcta.La cola de la recursividad es no optimizado por el compilador de Java o JVM.Usted siempre obtendrá un desbordamiento de pila con algo como esto:
int count(int i) {
return i >= 100000000 ? i : count(i+1);
}
Hay que tener en cuenta que la utilización de demasiado profundo recursividad que se ejecutará en el Desbordamiento de Pila, dependiendo permitido el tamaño de la pila.Para evitar esto, asegúrese de proporcionar algún caso base que finaliza la recursividad.
La recursividad tiene la desventaja de que el algoritmo que escriba el uso de la recursividad tiene O(n) en el espacio de la complejidad.Mientras que el enfoque iterativo tener un espacio complejidad de O(1).Este es el advantange de uso de la iteración a través de la recursividad.Entonces, ¿por qué no utilizamos la recursividad?
Ver a continuación.
A veces es más fácil escribir un algoritmo utilizando recursividad, mientras que es un poco más difícil de escribir el mismo algoritmo utilizando la iteración.En este caso, si optan por seguir la iteración enfoque tendría que manejar la pila de sí mismo.
Hasta donde yo sé, Perl no optimizar la cola de llamadas recursivas, pero se puede fingir.
sub f{
my($l,$r) = @_;
if( $l >= $r ){
return $l;
} else {
# return f( $l+1, $r );
@_ = ( $l+1, $r );
goto &f;
}
}
Cuando la primera llamada se va a asignar espacio en la pila.A continuación, se va a cambiar sus argumentos, y reiniciar la subrutina, sin agregar nada más a la pila.Por lo tanto, pretender que nunca llamó a su auto, cambiando en un proceso iterativo.
Tenga en cuenta que no hay ninguna "my @_;"o "local @_;"si usted lo hizo ya no funcionaría.
Utilizando sólo Chrome 45.0.2454.85 m, la recursividad parece ser una buena cantidad más rápido.
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 ejecuta utilizando el estándar de bucle
100x para el bucle se ejecutan.Tiempo para completar: 7.683 ms
// 100 ejecuta utilizando funcional recursiva enfoque w/ cola recursividad
100x recursividad ejecutar.Tiempo para completar: 4.841 ms
En la siguiente captura de pantalla, la recursividad gana de nuevo por un margen más elevado cuando se ejecuta en 300 ciclos por prueba
Si las iteraciones son atómicas y órdenes de magnitud más caro que empujar un nuevo marco de pila y la creación de un nuevo hilo y tiene varios núcleos y su entorno de tiempo de ejecución puede usar a todos ellos, entonces recursiva enfoque podría producir un gran aumento de rendimiento cuando se combina con subprocesamiento múltiple.Si el número medio de iteraciones no es previsible entonces podría ser una buena idea utilizar un conjunto de subprocesos que se va a controlar subproceso de asignación y evitar que el proceso de creación de demasiados hilos y acaparando el sistema.
Por ejemplo, en algunos idiomas, no son recursivos multiproceso de combinación de tipo de implementaciones.
Pero, de nuevo, subprocesamiento múltiple puede ser utilizado con un bucle en lugar de la recursividad, ¿qué tan bien esta combinación depende de más factores, incluyendo el sistema operativo y su hilo mecanismo de asignación.
Voy a responder a su pregunta por el diseño de un Haskell estructura de datos por "inducción", que es una especie de "doble" de la recursividad.Y, a continuación, voy a mostrar cómo esta dualidad lleva a cosas buenas.
Se introduce un tipo para un simple árbol:
data Tree a = Branch (Tree a) (Tree a)
| Leaf a
deriving (Eq)
Podemos leer esta definición como diciendo: "Un árbol es una Rama (que contiene dos árboles) o es una hoja (que contiene un valor de datos)".De modo que la hoja es una especie de mínimo caso.Si un árbol no es una hoja, entonces debe ser un compuesto de árbol que contiene dos árboles.Estos son los únicos casos.
Vamos a hacer un árbol:
example :: Tree Int
example = Branch (Leaf 1)
(Branch (Leaf 2)
(Leaf 3))
Ahora, supongamos que queremos sumar 1 a cada valor en el árbol.Podemos hacer esto llamando a:
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 datos de los constructores de la Rama y la Hoja de los casos (y ya que la Hoja es mínima y estos son los únicos casos posibles), estamos seguros de que la función va a terminar.
¿Qué se necesitaría para escribir addOne en un proceso iterativo de estilo?Lo que va a insertar en bucle en un número arbitrario de las ramas parecen?
También, este tipo de recursividad puede tomarse, en términos de una "functor".Podemos hacer Árboles en Functors mediante la definición de:
instance Functor Tree where fmap f (Leaf a) = Leaf (f a)
fmap f (Branch a b) = Branch (fmap f a) (fmap f b)
y la definición de:
addOne' = fmap (+1)
Podemos factor a cabo otras recursividad esquemas, tales como la catamorphism (o a veces) de una expresión algebraica tipo de datos.El uso de un catamorphism, podemos escribir:
addOne'' = cata go where
go (Leaf a) = Leaf (a + 1)
go (Branch a b) = Branch a b
Desbordamiento de pila sólo se producirá si eres de programación en un lenguaje que no se han construido en la gestión de memoria....De lo contrario, asegúrese de que usted tiene algo en su función (o una llamada a una función, STDLbs, etc).Sin recursividad simplemente no sería posible tener cosas como...Google o SQL, o en cualquier lugar que uno debe ordenar de manera eficiente a través de grandes estructuras de datos (clases) o bases de datos.
La recursividad es el camino a seguir si usted desea iterar a través de los archivos, bastante seguro de que es como " buscar * | ?grep *' obras.Un poco de doble recursividad, especialmente con la tubería (pero no de hacer un montón de llamadas al sistema como tantas como hacer si es algo que vas a poner ahí para que otros la utilicen).
Lenguajes de alto nivel e incluso clang/cpp puede realizar el mismo en el fondo.
