it-swarm-es.tech

¿Recursión o iteración?

¿Hay un impacto en el rendimiento si usamos un 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 un 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?

205
Omnipotent

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 una llamada recursiva). Recursión de cola debe ser reconocido por el compilador y optimizado 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 es el más claro para el pobre tonto (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 pasando a una implementación iterativa. Es posible que desee ver en memoization y programación dinámica .

173
Paul Osborne

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!

298
Leigh Caldwell

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, ¿verdad?

Algunos algoritmos 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 usan la "Evaluación perezosa", lo 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 conjunto de datos de gran tamaño utilizando PHP. Muestra lo fácil que habría sido tratar con Haskel usando 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

Link 2: Mastering Recursion

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".

https://developer.ibm.com/articles/l-recurs/

Enlace 3: ¿Es la recursión cada vez más rápida que el bucle? (Respuesta)

Aquí hay un enlace a una respuesta para una pregunta de stackoverflow 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 idioma. Los lenguajes imperativos suelen ser más rápidos usando un bucle y más lentos con recursión y viceversa para los 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.

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

76
Swift

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.

16
Doron Yaacoby

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 los 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 cola, etc. en.)

Aparte de los casos "Edge" (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.

11
zweiterlinde

La recursión es mejor que la iteración para los problemas que pueden dividirse en múltiples , piezas más pequeñas.

Por ejemplo, para hacer un algoritmo de Fibonnaci recursivo, 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 principal se puede dividir en múltiples menores problemas de análisis de 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 se pueden dividir en múltiples problemas más pequeños, independientes e similares.

8
Ben

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, los parámetros de llamada, otra información de contexto como los registros del procesador pueden guardarse en algún lugar 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.

7
entzik

Creo que la recursión de cola en Java no está optimizada actualmente. Los detalles se esparcen a lo largo de this discusión en LtU y los enlaces asociados. Puede puede ser una característica en la próxima versión 7, pero aparentemente presenta ciertas dificultades cuando se combina con Stack Inspection, ya que faltan algunos marcos. Stack Inspection se ha utilizado para implementar su modelo de seguridad detallado desde Java 2.

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

6
Mike Edwards

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 a que el caché mejoró el rendimiento.

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.

5
Nikunj Banka

Hay muchos casos en los que ofrece 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.

5
Felix

La recursividad 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.

5
Harikrishnan

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

4
mc

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. Por lo tanto, 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.

4
MovEaxEsp

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

4
Warrior

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 Turing-complete con solo un par de combinadores (sí, incluso una recursión en sí misma es una noción derivada de dicho sistema). Lambda el cálculo es un sistema fundamental igualmente poderoso, con funciones recursivas. Pero si desea definir una iteración correctamente, necesitaría mucho más primitivos para comenzar.

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 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 similares.

3
SK-logic

Si solo estás iterando sobre una lista, seguro, 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.

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

3
Joe Cheng

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).

2
metadave

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 indicadores de optimización como -O3 o -O2 en g++, entonces las recursiones pueden tener la posibilidad de ser más rápidas que las iteraciones. En los códigos iterativos, el compilador tiene menos posibilidades de optimizarlo, ya que está en el 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 templadas y he calculado 1,000,00012x12 matrices 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.

2
Titas Chanda

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. Quizás no encuentres un uso de inmediato o con frecuencia, pero habrá un problema que te alegrará que esté disponible.

2
Nickz

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 estoy haciendo ^ _ ^)

2
ugasoft

Mike tiene razón. La recursión de la cola es no optimizada por el compilador de Java o la JVM. Siempre obtendrás un desbordamiento de pila con algo como esto:

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

La recursión tiene la desventaja de que el algoritmo que escribe utilizando recursión tiene O(n) complejidad de espacio. 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.

1

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.

1
Grigori A.

Por lo que sé, 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.

0
Brad Gilbert

Si las iteraciones son atómicas y órdenes de magnitud son más caras que empujar un nuevo marco de pila y crear un nuevo hilo y tiene múltiples núcleos y su entorno 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 el funcionamiento de esta combinación depende de más factores, incluido el sistema operativo y su mecanismo de asignación de subprocesos.

0
ccpizza

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 de abajo, la recursión gana nuevamente por un margen mayor cuando se ejecuta a 300 ciclos por prueba

 Recursion wins again! 

0
Alpha G33k