¿Hay un impacto en el rendimiento si usamos un bucle en lugar de recurrencia o viceversa en algoritmos donde ambos pueden servir para el mismo propósito? Por ejemplo: Compruebe si la cadena dada es un palíndromo. He visto a muchos programadores usar la recursividad como un medio para mostrar cuándo un algoritmo de iteración simple puede ajustarse a la factura. ¿El compilador juega un papel vital en la decisión de qué usar?

Es posible que la recursividad sea más costosa, dependiendo de si la función recursiva es recursiva de cola (la última línea es llamada recursiva). La compilación de la cola debe ser reconocida por el compilador y optimizada para su contraparte iterativa (manteniendo la implementación concisa y clara 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 imbécil pobre (ya sea usted mismo o alguien más) que tiene 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 al pasar a una implementación iterativa. Es posible que desee examinar la memorización y la programación dinámica .

Los bucles pueden lograr una ganancia de rendimiento para su programa. La recursión puede lograr una ganancia de rendimiento para su programador. ¡Elija cuál es más importante en su situación!

Comparar la recursividad 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 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 conciso y fácil de entender (por lo tanto, compartible y reutilizable).

Además, algunos algoritmos recursivos usan "Evaluación perezosa" que los hace más eficientes que sus hermanos iterativos. Esto significa que solo hacen los costosos cálculos en el momento en que se necesitan y no cada vez que se ejecuta el ciclo.

Eso debería ser suficiente para comenzar. También buscaré algunos artículos y ejemplos para ti.

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. Él muestra lo fácil que hubiera sido lidiar en Haskel usando la recursión, pero como 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 en los idiomas imperativos. El autor de este artículo habla sobre cómo optimizar algoritmos recursivos para que sean más rápidos y más eficientes. También repasa cómo convertir un bucle tradicional en una función recursiva y los beneficios de usar la recursividad final. Sus palabras finales realmente resumieron algunos de mis puntos clave, creo:

"La programación recursiva le da al programador una mejor manera de organizar el código de una manera que sea mantenible y lógicamente consistente".

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

Enlace 3: ¿La recursividad es cada vez 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 suya. El autor señala que muchos de los puntos de referencia asociados con el recursivo o el bucle son muy específicos del lenguaje. Los lenguajes imperativos suelen ser más rápidos usando un bucle y más lento con recursión y viceversa para lenguajes funcionales. Supongo que el punto principal de este enlace es que es muy difícil responder la pregunta en un sentido de lenguaje agnóstico / situación ciega.

¿La recursividad es cada vez más rápida que el bucle?

La recursión es más costosa en la memoria, ya que cada llamada recursiva generalmente requiere que se introduzca una dirección de memoria en la pila, para que luego el programa pueda volver a ese punto.

Aún así, hay muchos casos en los que la recursividad 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.

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 pila adicionales; La penalización por esto varía. Además, en algunos lenguajes como Python (más correctamente, en algunas implementaciones de algunos lenguajes ...), puede encontrar límites de pila con bastante facilidad para tareas que podría 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 de rendimiento, suponiendo que tenga un compilador que optimice las recursiones de cola, etc. en.)

Además de los casos "límite" (informática 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 mantenible. Optimice solo después de identificar una necesidad.

La recursión 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, descompone fib (n) en fib (n-1) y fib (n-2) y calcula 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 analizar cada nodo hijo. A diferencia del ejemplo de Fibonacci, los problemas más pequeños son independientes entre sí.

Entonces, sí, la recursión es mejor que la iteración para problemas que se pueden dividir en múltiples, más pequeños, independientes, problemas similares.

Su rendimiento se deteriora cuando usa la recursividad 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, alguna otra información de contexto, como registros de procesador, puede guardarse en algún lugar, y en el momento de la devolución el el método llamado publica un valor de retorno que luego es recuperado por la persona que llama, y ​​cualquier información de contexto que se haya guardado previamente se restaurará. La diferencia de rendimiento entre un enfoque iterativo y uno recursivo radica en el tiempo que toman estas operaciones.

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

Creo que la recursividad de la cola en Java no está optimizada actualmente. Los detalles se rocían a lo largo de esta discusión sobre LtU y los enlaces asociados. se 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 ya que ciertos marcos estarían ausentes. Stack Inspection se ha utilizado para implementar su modelo de seguridad detallado desde Java 2.

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

Hay muchos casos en los que ofrece una solución mucho más elegante sobre 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 simples de comprender e implementar correctamente.

La recursión 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é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 muy propenso a errores. Supongamos que si extrañamosif (input == 0) , el código se ejecutará durante un tiempo y generalmente termina con un desbordamiento de la pila.

En muchos casos, la recursividad es más rápida debido al almacenamiento en caché, que mejora el rendimiento. Por ejemplo, aquí hay una versión iterativa del tipo de fusión usando la rutina de fusión tradicional. Se ejecutará más lentamente que la implementación recursiva debido al almacenamiento en caché de mejores actuaciones.

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.

Usando la recursión, usted está incurriendo en el costo de una llamada de función con cada "iteración", mientras que con un bucle, lo único que generalmente paga es un incremento / decremento. Entonces, si el código del bucle no es mucho más complicado que el código de la solución recursiva, el bucle generalmente será superior a la recursividad.

La recursión y la iteración dependen de la lógica empresarial que desea 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 deberías usar bucles. Los lenguajes funcionales optimizan la recursividad.

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

Un par de otras respuestas han mencionado el recorrido del árbol (primero en profundidad). Realmente es un gran ejemplo, porque es algo muy común hacer 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

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 en dicho sistema). Lambda cálculo es un sistema fundamental igualmente poderoso, con funciones recursivas. Pero si desea definir una iteración correctamente, necesitaría muchas más primitivas 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 una manera ordenada. En C ++, por supuesto, las soluciones recursivas complicadas pueden verse un poco feas, a menos que sea un usuario incondicional de FC ++ y similares.

Creo que en la recursión (no de cola) habría un impacto en el rendimiento para asignar una nueva pila, etc., cada vez que se llama a la función (dependiendo del idioma, por supuesto).

depende de la "profundidad de recursión". depende de cuánto influirá la sobrecarga de la 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 pila - 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á N movimientos posteriores se puede implementar en forma recursiva sobre la "profundidad de análisis" (como estoy haciendo ^ _ ^)

Recursividad? ¿Por dónde empiezo? Wiki te dirá "es el proceso de repetir elementos de forma similar".

En el pasado, cuando estaba haciendo C, la recursión de C ++ fue un envío de Dios, cosas como "Recurrencia de cola". También encontrará que muchos algoritmos de clasificación usan la recursividad. Ejemplo de ordenació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á de que esté disponible.

En C ++ si la función recursiva es una plantilla, entonces el compilador tiene más posibilidades de optimizarla, ya que todas las instancias de deducción y función de tipo ocurrirán en tiempo de compilación. Los compiladores modernos también pueden incorporar la función si es posible. Entonces, si uno usa indicadores de optimización como -O3o -O2adentro 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 ya 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 de matrices al cuadrar usando objetos de matriz Armadillo, tanto de forma recursiva como iterativa. El algoritmo se puede encontrar aquí ... https://en.wikipedia.org/wiki/Exponentiation_by_squaring . Mis funciones fueron modeladas y he calculado 1,000,000 12x12matrices elevadas al poder 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 usando gcc-4.8 con c ++ 11 flag ( -std=c++11) y Armadillo 6.1 con Intel mkl. El compilador de Intel también muestra resultados similares.

Mike tiene razón. El compilador de Java o la JVM no optimiza la recursividad de cola . Siempre obtendrá un desbordamiento de pila con algo como esto:

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

Debe tener en cuenta que si utiliza una recursión demasiado profunda, se encontrará con el desbordamiento de la pila, según el tamaño de pila permitido. Para evitar esto, asegúrese de proporcionar un caso base que termine su recursión.

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 espacial de O (1), esta es la ventaja de utilizar la iteración sobre la recursividad. Entonces, ¿por qué usamos la recursividad?

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.

Si las iteraciones son atómicas y los órdenes de magnitud son más caros que presionar 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 generar un gran aumento de rendimiento cuando se combina con multihilo. Si el número promedio de iteraciones no es predecible, podría 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 recursivas de clasificación de fusión multiproceso.

Pero nuevamente, el subprocesamiento múltiple se puede usar con bucles en lugar de recursividad, 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.

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 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, pretenderá que nunca se llamó a sí mismo, transformándolo en un proceso iterativo.

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

Usando solo Chrome 45.0.2454.85 m, la recursión parece ser mucho 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 utilizando el estándar para el bucle

100x para el ciclo de ejecución. Tiempo para completar: 7.683ms

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

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

En la captura de pantalla a continuación, la recursión vuelve a ganar por un margen mayor cuando se ejecuta a 300 ciclos por prueba

Encontré otras diferencias entre esos enfoques. Parece simple y sin importancia, pero tiene un papel muy importante mientras te preparas para las entrevistas y surge este tema, así que mira de cerca.

En resumen: 1) el recorrido iterativo de orden posterior no es fácil, eso hace que DFT sea más complejo 2) los ciclos de verificación más fáciles con recursividad

Detalles:

En el caso recursivo, es fácil crear recorridos previos y posteriores:

Imagine una pregunta bastante estándar: "imprima todas las tareas que deben ejecutarse para ejecutar la tarea 5, cuando las tareas dependen de otras tareas"

Ejemplo:

    //key-task, value-list of tasks the key task depends on
    //"adjacency map":
    Map<Integer, List<Integer>> tasksMap = new HashMap<>();
    tasksMap.put(0, new ArrayList<>());
    tasksMap.put(1, new ArrayList<>());

    List<Integer> t2 = new ArrayList<>();
    t2.add(0);
    t2.add(1);
    tasksMap.put(2, t2);

    List<Integer> t3 = new ArrayList<>();
    t3.add(2);
    t3.add(10);
    tasksMap.put(3, t3);

    List<Integer> t4 = new ArrayList<>();
    t4.add(3);
    tasksMap.put(4, t4);

    List<Integer> t5 = new ArrayList<>();
    t5.add(3);
    tasksMap.put(5, t5);

    tasksMap.put(6, new ArrayList<>());
    tasksMap.put(7, new ArrayList<>());

    List<Integer> t8 = new ArrayList<>();
    t8.add(5);
    tasksMap.put(8, t8);

    List<Integer> t9 = new ArrayList<>();
    t9.add(4);
    tasksMap.put(9, t9);

    tasksMap.put(10, new ArrayList<>());

    //task to analyze:
    int task = 5;


    List<Integer> res11 = getTasksInOrderDftReqPostOrder(tasksMap, task);
    System.out.println(res11);**//note, no reverse required**

    List<Integer> res12 = getTasksInOrderDftReqPreOrder(tasksMap, task);
    Collections.reverse(res12);//note reverse!
    System.out.println(res12);

    private static List<Integer> getTasksInOrderDftReqPreOrder(Map<Integer, List<Integer>> tasksMap, int task) {
         List<Integer> result = new ArrayList<>();
         Set<Integer> visited = new HashSet<>();
         reqPreOrder(tasksMap,task,result, visited);
         return result;
    }

private static void reqPreOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {

    if(!visited.contains(task)) {
        visited.add(task);
        result.add(task);//pre order!
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPreOrder(tasksMap,child,result, visited);
            }
        }
    }
}

private static List<Integer> getTasksInOrderDftReqPostOrder(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    reqPostOrder(tasksMap,task,result, visited);
    return result;
}

private static void reqPostOrder(Map<Integer, List<Integer>> tasksMap, int task, List<Integer> result, Set<Integer> visited) {
    if(!visited.contains(task)) {
        visited.add(task);
        List<Integer> children = tasksMap.get(task);
        if (children != null && children.size() > 0) {
            for (Integer child : children) {
                reqPostOrder(tasksMap,child,result, visited);
            }
        }
        result.add(task);//post order!
    }
}

Tenga en cuenta que el recorrido recursivo posterior al pedido no requiere una inversión posterior del resultado. Los niños imprimieron primero y su tarea en la pregunta se imprimió al final. Todo esta bien. Puede hacer un recorrido recursivo de pre-orden (también se muestra arriba) y ese requerirá una inversión de la lista de resultados.

¡No es tan simple con un enfoque iterativo! En el enfoque iterativo (una pila) solo puede hacer un recorrido de preordenamiento, por lo que se vio obligado a invertir la matriz de resultados al final:

    List<Integer> res1 = getTasksInOrderDftStack(tasksMap, task);
    Collections.reverse(res1);//note reverse!
    System.out.println(res1);

    private static List<Integer> getTasksInOrderDftStack(Map<Integer, List<Integer>> tasksMap, int task) {
    List<Integer> result = new ArrayList<>();
    Set<Integer> visited = new HashSet<>();
    Stack<Integer> st = new Stack<>();


    st.add(task);
    visited.add(task);

    while(!st.isEmpty()){
        Integer node = st.pop();
        List<Integer> children = tasksMap.get(node);
        result.add(node);
        if(children!=null && children.size() > 0){
            for(Integer child:children){
                if(!visited.contains(child)){
                    st.add(child);
                    visited.add(child);
                }
            }
        }
        //If you put it here - it does not matter - it is anyway a pre-order
        //result.add(node);
    }
    return result;
}

Parece simple, no?

Pero es una trampa en algunas entrevistas.

Significa lo siguiente: con el enfoque recursivo, puede implementar Profund First Traversal y luego seleccionar el orden que necesita antes o después (simplemente cambiando la ubicación de la "impresión", en nuestro caso de "agregar a la lista de resultados" ) Con el enfoque iterativo (una pila), puede hacer fácilmente un recorrido transversal de preorden y, por lo tanto, en la situación en la que los niños necesitan imprimirse primero (casi todas las situaciones en las que necesita comenzar a imprimir desde los nodos inferiores, hacia arriba): está en el problema. Si tiene ese problema, puede revertirlo más tarde, pero será una adición a su algoritmo. Y si un entrevistador está mirando su reloj, puede ser un problema para usted. Existen formas complejas de hacer un recorrido iterativo de orden posterior, existen, pero no son simples . Ejemplo:https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

Por lo tanto, la conclusión: usaría la recursividad durante las entrevistas, es más fácil de manejar y explicar. Usted tiene una manera fácil de pasar de un recorrido pre a otro en cualquier caso urgente. Con iterativo no eres tan flexible.

Usaría la recursión y luego diría: "Ok, pero iterativo puede proporcionarme un control más directo sobre la memoria usada, puedo medir fácilmente el tamaño de la pila y no permitir algún desbordamiento peligroso ..."

Otra ventaja de la recursividad: es más sencillo evitar / notar ciclos en un gráfico.

Ejemplo (preudocódigo):

dft(n){
    mark(n)
    for(child: n.children){
        if(marked(child)) 
            explode - cycle found!!!
        dft(child)
    }
    unmark(n)
}

Puede ser divertido escribirlo como recursividad o como práctica.

Sin embargo, si el código se va a usar en producción, debe considerar la posibilidad de desbordamiento de pila.

La optimización de la recursividad de la cola puede eliminar el desbordamiento de la pila, pero ¿quiere pasar por la molestia de hacerlo así y necesita saber que puede contar con que tenga la optimización en su entorno?

Cada vez que se repite el algoritmo, ¿en cuánto se nreduce o reduce el tamaño de los datos ?

Si está reduciendo el tamaño de los datos o na la mitad cada vez que recurre, entonces, en general, no necesita preocuparse por el desbordamiento de la pila. Supongamos que si el programa tiene que tener un nivel de profundidad de 4000 o un nivel de profundidad de 10,000 para que el programa apile el desbordamiento, entonces su tamaño de datos debe ser aproximadamente 2 ⁴⁰⁰⁰ para que su programa apile el desbordamiento. Para poner esto en perspectiva, un dispositivo de almacenamiento más grande recientemente puede contener 2 ⁶¹ bytes, y si tiene 2 ⁶¹ de dichos dispositivos, solo está tratando con un tamaño de datos de 2 ¹²² . Si observa todos los átomos del universo, se estima que puede ser inferior a 2 ⁸⁴. Si necesita lidiar con todos los datos en el universo y sus estados por cada milisegundo desde el nacimiento del universo, estimado hace 14 mil millones de años, puede ser solo 2 ¹⁵³ . Entonces, si su programa puede manejar 2 ⁴⁰⁰⁰unidades de datos o n, puede manejar todos los datos en el universo y el programa no se acumulará desbordamiento. Si no necesita lidiar con números que son tan grandes como 2 ⁴⁰⁰⁰ (un entero de 4000 bits), entonces, en general, no necesita preocuparse por el desbordamiento de la pila.

Sin embargo, si reduce el tamaño de los datos o nen una cantidad constante cada vez que recurre, entonces puede encontrarse con un desbordamiento de pila cuando su programa se ejecuta bien cuando nes, 1000pero en alguna situación, cuando se nvuelve meramente 20000.

Entonces, si tiene una posibilidad de desbordamiento de la pila, intente que sea una solución iterativa.

Voy a responder a su pregunta diseñando una estructura de datos de Haskell por "inducción", que es una especie de "dual" 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 como 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, 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 a:

addOne :: Tree Int -> Tree Int
addOne (Branch a b) = 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í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? ¿Cómo se verá el 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 "functor". Podemos convertir los árboles en functores 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 algebraicos. Usando un catamorfismo, podemos escribir:

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

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

La recursión es el camino a seguir si desea recorrer los archivos, bastante seguro de que es así 'find * | ? grep * 'funciona. Un poco de doble recursión, especialmente con la tubería (pero no hagas un montón de llamadas de sistema como a muchos 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 segundo plano.