Recursión o iteración?

¿Hay un golpe de rendimiento si usamos loop en lugar de recursión o viceversa en algoritmos donde ambos pueden servir para el mismo propósito? Ejemplo: comprobar si la cadena dada es palíndromo. He visto a muchos progtwigdores usar la recursividad como un medio para presumir cuando un algoritmo de iteración simple puede ajustarse a la factura. ¿El comstackdor juega un papel vital al decidir qué usar?

Es posible que la recursión sea más costosa, dependiendo de si la función recursiva es recursiva de cola (la última línea es una llamada recursiva). La recurrencia de cola debe ser reconocida por el comstackdor y optimizada para su contraparte iterativa (mientras mantiene la implementación concisa y clara que tiene en su código).

Escribiría el algoritmo de la forma que tenga más sentido y sea más clara para el pobre imbécil (sea usted mismo o alguien más) que tenga que mantener el código en unos pocos meses o años. Si se encuentra con problemas de rendimiento, perfile su código, y luego, y solo entonces, busque la optimización pasando a una implementación iterativa. Es posible que desee examinar la memorización y la progtwigción dinámica .

Los bucles pueden lograr un aumento de rendimiento para su progtwig. La recursividad puede lograr un aumento de rendimiento para su progtwigdor. ¡Elija cuál es más importante en su situación!

Comparar la recursión con la iteración es como comparar un destornillador phillips con un destornillador de cabeza plana. En su mayor parte, podría quitar cualquier tornillo de cabeza Phillips con una cabeza plana, pero sería más fácil si utilizó el destornillador diseñado para ese tornillo, ¿verdad?

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 tipo árbol, etc.). La recursividad 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 usan “Evaluación diferida” que los hace más eficientes que sus hermanos iterativos. Esto significa que solo hacen los costosos cálculos en el momento en que son necesarios en lugar de cada vez que se ejecuta el ciclo.

Eso debería ser suficiente para comenzar. 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 progtwigdor tuvo que procesar un gran conjunto de datos usando PHP. Él muestra cuán fácil habría sido tratar en Haskel usando la recursión, pero como PHP no tenía una manera fácil de lograr el mismo método, se vio forzado a usar la iteración para obtener el resultado.

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

Enlace 2: Mastering Recursion

La mayor parte de la mala reputación de la recursión proviene de los altos costos y la ineficiencia en los lenguajes 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 repasa 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 resumen algunos de mis puntos clave, creo:

“La progtwigción recursiva le brinda al progtwigdor una mejor forma de organizar el código de una manera que es mantenible y 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 stackoverflow que es similar a la tuya. El autor señala que muchos de los puntos de referencia asociados con la recursión o el bucle son muy específicos del idioma. Los lenguajes imperativos suelen ser más rápidos utilizando un ciclo y más lentos con la recursión y viceversa para los lenguajes funcionales. Supongo que el punto principal a tomar de este enlace es que es muy difícil responder a la pregunta en un sentido del lenguaje agnóstico / situación a ciegas.

¿La recursión es más rápida que el bucle?

La recursividad es más costosa en la memoria, ya que cada llamada recursiva generalmente requiere que se envíe una dirección de memoria a la stack, para que luego el progtwig pueda regresar a ese punto.

Aún así, 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 seguir con la recursión.

Típicamente, 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 stack adicionales; la pena por esto varía. Además, en algunos lenguajes como Python (más correctamente, en algunas implementaciones de algunos idiomas …), puede ejecutar los límites de la stack bastante fácilmente para tareas que puede especificar recursivamente, como encontrar el valor máximo en una estructura de datos de árbol. En estos casos, realmente desea seguir con los bucles.

Escribir buenas funciones recursivas puede reducir algo la penalización del rendimiento, suponiendo que tiene un comstackdor que optimiza las repeticiones de cola, etc. (También verifique dos veces para asegurarse de que la función realmente es recursiva de cola; es una de esas cosas en las que mucha gente comete errores). en.)

Además de los casos de “borde” (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 sea fácil de mantener. Optimizar solo después de identificar una necesidad.

La recursividad es mejor que la iteración para problemas que se pueden dividir en múltiples piezas más pequeñas.

Por ejemplo, para hacer un algoritmo recursivo de Fibonnaci, se divide 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 padre se puede dividir en múltiples problemas más pequeños de análisis de cada nodo hijo. 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 para problemas que pueden descomponerse en problemas múltiples, más pequeños, independientes y similares.

Su rendimiento se deteriora al usar la recursividad porque llamar a un método, en cualquier idioma, implica mucha preparación: el código de llamada muestra una dirección de retorno, parámetros de llamada, alguna otra información de contexto como registros de procesador pueden guardarse en algún lugar, y en el momento el método llamado contabiliza un valor de retorno que luego recupera la persona que llama y se restaura la información de contexto que se guardó anteriormente. la diferencia de rendimiento entre un enfoque iterativo y recursivo radica en el tiempo que tardan estas operaciones.

Desde el punto de vista de la implementación, realmente comienzas a notar la diferencia cuando el tiempo necesario para manejar el contexto de la llamada es comparable al tiempo que tarda tu método en ejecutarse. Si su método recursivo tarda más tiempo en ejecutarse, entonces la parte de administración del contexto llamante sigue el camino recursivo, 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, será iterativo por razones de eficiencia.

Creo que la recursividad de cola en Java no está actualmente optimizada. Los detalles se rocían a lo largo de esta discusión en 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 stack, ya que faltan ciertos marcos. Stack Inspection se ha utilizado para implementar su modelo de seguridad de grano fino desde Java 2.

http://lambda-the-ultimate.org/node/1333

Hay muchos casos en los que ofrece una solución mucho más elegante que el método iterativo, siendo el ejemplo común el cruce 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 fáciles de comprender e implementar 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 considéralo 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 errores. Supongamos que si omitimos if (input == 0) , entonces el código se ejecutará durante un tiempo y termina generalmente con un desbordamiento de la stack.

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 merge sort usando la rutina de combinación tradicional. Funcionará más lento que la implementación recursiva debido a las prestaciones mejoradas de almacenamiento en caché.

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.

Al utilizar recursividad, incurre en el costo de una llamada a función con cada “iteración”, mientras que con un ciclo, lo único que suele pagar 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.

La recursividad y la iteración dependen de la lógica comercial que desee implementar, aunque en la mayoría de los casos se puede usar indistintamente. La mayoría de los desarrolladores recurren a la recursividad porque es más fácil de entender.

Depende del idioma En Java debes usar loops. Los lenguajes funcionales optimizan la recursividad.

Si solo estás iterando sobre una lista, entonces seguro, itera.

Un par de otras respuestas han mencionado (cruce de árbol en profundidad). Realmente es un gran ejemplo, porque es algo muy común de hacer a una estructura de datos muy común. La recursividad es extremadamente intuitiva para este problema.

Consulte los métodos de “búsqueda” aquí: http://penguin.ewu.edu/cscd300/Topic/BSTintro/index.html

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 de Turing-complete con solo un par de combinadores (sí, incluso una recursividad en sí misma es una noción derivada de dicho sistema). El cálculo Lambda es un sistema fundamental igualmente poderoso, que presenta funciones recursivas. Pero si quieres definir una iteración correctamente, necesitarías muchas más primitivas 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 necesitaría un lenguaje con soporte para funciones de alto orden y cierres, al menos, para obtener todos los combinadores e iteradores estándar de una manera ordenada. En C ++, por supuesto, las soluciones recursivas complicadas pueden parecer un poco feas, a menos que seas un usuario duro de FC ++ y similares.

Creo que en la recursividad (sin cola) habría un golpe de rendimiento para asignar una nueva stack, etc. cada vez que se llama a la función (dependiendo del lenguaje, por supuesto).

depende de la “profundidad de recursión”. depende de cuánto influya la sobrecarga de llamada de función en el tiempo total de ejecución.

Por ejemplo, calcular el factorial clásico de forma recursiva es muy ineficiente debido a: – riesgo de desbordamiento de datos – riesgo de desbordamiento de la stack – la sobrecarga de llamadas de función ocupa el 80% del tiempo de ejecución

mientras se desarrolla un algoritmo min-max para el análisis de posición en el juego de ajedrez que analizará movimientos subsiguientes de N se puede implementar en recursión sobre la “profundidad de análisis” (como lo estoy haciendo ^ _ ^)

Recursión? ¿Por dónde empiezo? Wiki te dirá “es el proceso de repetir ítems de manera similar”

De regreso en el día cuando estaba haciendo C, la recursión de C ++ era un envío de dios, cosas como “recursividad de cola”. También encontrará muchos algoritmos de clasificación que usan recursividad. 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 encuentres un uso enseguida o con frecuencia, pero habrá un problema que te alegrará de que esté disponible.

En C ++, si la función recursiva es una plantilla, entonces el comstackdor tiene más posibilidades de optimizarla, ya que todas las instancias de deducción y funciones de tipo ocurrirán en tiempo de comstackción. Los comstackdores modernos también pueden alinear la función si es posible. Entonces, si uno usa indicadores de optimización como -O2 o -O2 en g++ , las recursiones pueden tener la posibilidad de ser más rápidas que las iteraciones. En los códigos iterativos, el comstackdor tiene menos posibilidades de optimizarlo, dado que ya se encuentra en un estado más o menos óptimo (si se lo escribe suficientemente bien).

En mi caso, estaba tratando de implementar la exponenciación matricial cuadrando usando objetos de matriz de Armadillo, tanto de forma recursiva como iterativa. Algoritmo se puede encontrar aquí … https://en.wikipedia.org/wiki/Exponentiation_by_squaring . Mis funciones fueron modeladas 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 obtuvieron utilizando gcc-4.8 con el indicador c ++ 11 ( -std=c++11 ) y Armadillo 6.1 con Intel mkl. El comstackdor de Intel también muestra resultados similares.

Mike es correcto La recursividad de cola no está optimizada por el comstackdor de Java o la JVM. Siempre obtendrás un desbordamiento de stack con algo como esto:

 int count(int i) { return i >= 100000000 ? i : count(i+1); } 

Debe tener en cuenta que al utilizar una recurrencia demasiado profunda se encontrará con el Desbordamiento de stack, dependiendo del tamaño de stack permitido. Para evitar esto, asegúrese de proporcionar un caso base que finaliza la recursión.

La recursión tiene la desventaja de que el algoritmo que se escribe utilizando recursión tiene una complejidad de espacio O (n). Mientras que el enfoque iterativo tiene una complejidad espacial 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 utilizando 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, deberá manejar la stack usted mismo.

Hasta donde yo sé, Perl no optimiza las llamadas recursivas de cola, pero puedes fingirlo.

 sub f{ my($l,$r) = @_; if( $l >= $r ){ return $l; } else { # return f( $l+1, $r ); @_ = ( $l+1, $r ); goto &f; } } 

Cuando se lo llame por primera vez asignará espacio en la stack. Luego cambiará sus argumentos y reiniciará la subrutina, sin agregar nada más a la stack. Por lo tanto, pretenderá que nunca se llamó a sí mismo, convirtiéndolo en un proceso iterativo.

Tenga en cuenta que no hay ” my @_; ” o ” local @_;local @_; si lo hiciera, ya no funcionaría.

Si las iteraciones son atómicas y mucho más costosas que empujar un nuevo marco de stack y crear un nuevo hilo y tienes múltiples núcleos y tu entorno de tiempo de ejecución puede usarlos todos, entonces un enfoque recursivo podría generar un gran aumento de rendimiento cuando se combina con multihilo. Si el número promedio de iteraciones no es predecible, puede ser una buena idea usar un grupo de subprocesos que controle la asignación de subprocesos y evite que su proceso cree demasiados subprocesos y acapare el sistema.

Por ejemplo, en algunos idiomas hay implementaciones de ordenación de mezcla multiproceso recursivas.

Pero, de nuevo, el multihilo se puede usar con bucle en lugar de recursión, entonces, ¿cómo funcionará esta combinación depende de más factores, incluido el sistema operativo y su mecanismo de asignación de hilos.

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 ejecuciones usando el bucle estándar para

100x para ejecución de bucle Tiempo para completar: 7.683ms

// 100 ejecuciones usando un enfoque recursivo funcional con recursión de cola

Ejecución de recursión 100x. Tiempo para completar: 4.841ms

En la captura de pantalla siguiente, la recursividad gana nuevamente por un margen mayor cuando se ejecuta a 300 ciclos por prueba

¡La recursión gana de nuevo!

Voy a responder a tu pregunta diseñando una estructura de datos Haskell por “inducción”, que es una especie de “doble” a la recursión. Y luego mostraré cómo esta dualidad conduce a cosas agradables.

Presentamos 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)”. Entonces, la hoja es una especie de caso mínimo. Si un árbol no es una hoja, entonces debe ser un árbol compuesto que contenga 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 hacer esto llamando:

 addOne :: Tree Int -> Tree Int addOne (Branch ab) = Branch (addOne a) (addOne b) addOne (Leaf a) = Leaf (a + 1) 

Primero, observe que esta es de hecho una definición recursiva. Toma los constructores de datos Branch y Leaf como casos (y dado que Leaf es mínima 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? ¿Cómo se verá el bucle en un número arbitrario de twigs?

Además, este tipo de recursión a menudo se puede tener en cuenta, en términos de un “functor”. Podemos convertir Árboles en Funcionadores definiendo:

 instance Functor Tree where fmap f (Leaf a) = Leaf (fa) fmap f (Branch ab) = Branch (fmap fa) (fmap fb) 

y definiendo:

 addOne' = fmap (+1) 

Podemos factorizar otros esquemas de recursión, como el catamorfismo (o pliegue) para un tipo de datos algebraicos. Usando un catamorfismo, podemos escribir:

 addOne'' = cata go where go (Leaf a) = Leaf (a + 1) go (Branch ab) = Branch ab 

El desbordamiento de stack solo ocurrirá si está progtwigndo en un idioma que no tiene administración de memoria incorporada … De lo contrario, asegúrese de tener algo en su función (o una llamada a función, STDLbs, etc.). Sin recursión, simplemente no sería posible tener cosas como … Google o SQL, o en cualquier lugar, uno debe clasificar eficientemente a través de grandes estructuras de datos (clases) o bases de datos.

La recursividad es el camino a seguir si quiere iterar a través de los archivos, bastante seguro de que así es como ‘find * | ? grep * ‘funciona. Una especie de doble recursión, especialmente con la tubería (pero no hagas un montón de llamadas de sistema como a tantas les gusta hacer si es algo que vas a poner allí para que otros lo usen).

Los lenguajes de nivel superior e incluso clang / cpp pueden implementarlo de la misma manera en el fondo.