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

Sé que la recursión a veces es mucho más limpia que el bucle, y no estoy preguntando nada sobre cuándo debería usar la recursión sobre la iteración, sé que ya hay muchas preguntas al respecto.

Lo que pregunto es si la recursividad es cada vez más rápida que un bucle. Para mí, parece que siempre podrá refinar un bucle y lograr que funcione más rápido que una función recursiva porque el bucle está ausente constantemente configurando nuevos cuadros de pila.

Estoy buscando específicamente si la recursividad es más rápida en aplicaciones donde la recursividad es la forma correcta de manejar los datos, como en algunas funciones de clasificación, en árboles binarios, etc.

Esto depende del idioma utilizado. Escribiste 'language-agnostic', así que daré algunos ejemplos.

En Java, C y Python, la recursión es bastante cara en comparación con la iteración (en general) porque requiere la asignación de un nuevo marco de pila. En algunos compiladores de C, se puede usar un indicador de compilador para eliminar esta sobrecarga, que transforma ciertos tipos de recursión (en realidad, ciertos tipos de llamadas de cola) en saltos en lugar de llamadas de función.

En implementaciones de lenguaje de programación funcional, a veces, la iteración puede ser muy costosa y la recursión puede ser muy barata. En muchos casos, la recursión se transforma en un salto simple, pero a veces se cambia la variable del bucle (que es mutable) requiere algunas operaciones relativamente pesadas, especialmente en implementaciones que admiten múltiples hilos de ejecución. La mutación es costosa en algunos de estos entornos debido a la interacción entre el mutador y el recolector de basura, si ambos pueden estar ejecutándose al mismo tiempo.

Sé que en algunas implementaciones de Scheme, la recursión generalmente será más rápida que el bucle.

En resumen, la respuesta depende del código y la implementación. Usa el estilo que prefieras. Si está utilizando un lenguaje funcional, la recursividad podría ser más rápida. Si está utilizando un lenguaje imperativo, la iteración es probablemente más rápida. En algunos entornos, ambos métodos generarán el mismo ensamblaje (colóquelo en la tubería y fúmalo).

Anexo: en algunos entornos, la mejor alternativa no es la recursividad ni la iteración, sino funciones de orden superior. Estos incluyen "mapa", "filtro" y "reducir" (que también se llama "plegar"). Estos no solo son el estilo preferido, no solo son a menudo más limpios, sino que en algunos entornos estas funciones son las primeras (o únicas) que reciben un impulso de la paralelización automática, por lo que pueden ser significativamente más rápidas que la iteración o la recursión. Data Parallel Haskell es un ejemplo de dicho entorno.

Las comprensiones de listas son otra alternativa, pero generalmente son solo azúcar sintáctico para iteración, recursión o funciones de orden superior.

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

No, la iteración siempre será más rápida que la recursividad. (en una arquitectura de Von Neumann)

Explicación:

Si crea las operaciones mínimas de una computadora genérica desde cero, la "iteración" viene primero como un bloque de construcción y requiere menos recursos que la "recursividad", ergo es más rápido.

Construir una máquina de pseudocomputación desde cero:

Pregúntese : ¿Qué necesita para calcular un valor, es decir, para seguir un algoritmo y alcanzar un resultado?

Estableceremos una jerarquía de conceptos, comenzando desde cero y definiendo en primer lugar los conceptos básicos y básicos, luego construiremos conceptos de segundo nivel con ellos, y así sucesivamente.

1. Primer concepto: celdas de memoria, almacenamiento, estado . Para hacer algo, necesita lugares para almacenar valores de resultados finales e intermedios. Supongamos que tenemos una matriz infinita de celdas "enteras", llamadas Memoria , M [0..Infinito].

2. Instrucciones: haz algo: transforma una celda, cambia su valor. Alterar el estado . Cada instrucción interesante realiza una transformación. Las instrucciones básicas son:

   una) Establecer y mover celdas de memoria

   • almacenar un valor en la memoria, por ejemplo: almacenar 5 m [4]
   • copiar un valor a otra posición: por ejemplo: almacenar m [4] m [8]

   si) Lógica y aritmética.

   • y, o, xor, no
   • sumar, sub, mul, div. por ejemplo, agregue m [7] m [8]

3. Un agente ejecutor : un núcleo en una CPU moderna. Un "agente" es algo que puede ejecutar instrucciones. Un agente también puede ser una persona que sigue el algoritmo en papel.

4. Orden de pasos: una secuencia de instrucciones : es decir: hacer esto primero, hacer esto después, etc. Una secuencia imperativa de instrucciones. Incluso las expresiones de una línea son "una secuencia imperativa de instrucciones". Si tiene una expresión con un "orden de evaluación" específico, entonces tiene pasos . Significa que incluso una sola expresión compuesta tiene "pasos" implícitos y también tiene una variable local implícita (llamémosla "resultado"). p.ej:

   4 + 3 * 2 - 5
   (- (+ (* 3 2) 4 ) 5)
   (sub (add (mul 3 2) 4 ) 5)  
   

   La expresión anterior implica 3 pasos con una variable "resultado" implícita.

   // pseudocode
   
          1. result = (mul 3 2)
          2. result = (add 4 result)
          3. result = (sub result 5)
   

   Entonces, incluso las expresiones infijadas, dado que tiene un orden específico de evaluación, son una secuencia imperativa de instrucciones . La expresión implica una secuencia de operaciones a realizar en un orden específico, y debido a que hay pasos , también hay una variable intermedia "resultado" implícita.

5. Puntero de instrucción : si tiene una secuencia de pasos, también tiene un "puntero de instrucción" implícito. El puntero de instrucción marca la siguiente instrucción y avanza después de leer la instrucción pero antes de que se ejecute.

   En esta máquina de seudocomputación, el puntero de instrucción forma parte de la memoria . (Nota: Normalmente, el puntero de instrucción será un "registro especial" en un núcleo de CPU, pero aquí simplificaremos los conceptos y asumiremos que todos los datos (registros incluidos) son parte de "Memoria")

6. Saltar : una vez que tenga un número ordenado de pasos y un puntero de instrucción , puede aplicar la instrucción " almacenar " para modificar el valor del puntero de instrucción. Llamaremos a este uso específico de las instrucciones de la tienda con un nuevo nombre: Jump . Usamos un nuevo nombre porque es más fácil pensarlo como un nuevo concepto. Al alterar el puntero de instrucciones, le estamos indicando al agente que "vaya al paso x".

7. Iteración infinita : al saltar hacia atrás, ahora puede hacer que el agente "repita" una cierta cantidad de pasos. En este punto tenemos iteración infinita.

                      1. mov 1000 m[30]
                      2. sub m[30] 1
                      3. jmp-to 2  // infinite loop
   

8. Condicional : ejecución condicional de instrucciones. Con la cláusula "condicional", puede ejecutar condicionalmente una de varias instrucciones en función del estado actual (que se puede establecer con una instrucción previa).

9. Iteración adecuada : ahora con la cláusula condicional , podemos escapar del bucle infinito de la instrucción de salto hacia atrás . Ahora tenemos un bucle condicional y luego una iteración adecuada

   1. mov 1000 m[30]
   2. sub m[30] 1
   3. (if not-zero) jump 2  // jump only if the previous 
                           // sub instruction did not result in 0
   
   // this loop will be repeated 1000 times
   // here we have proper ***iteration***, a conditional loop.
   

10. Naming : dar nombres a una ubicación de memoria específica que contiene datos o que mantiene un paso . Esto es solo una "conveniencia" de tener. No agregamos ninguna instrucción nueva al tener la capacidad de definir "nombres" para ubicaciones de memoria. "Nombrar" no es una instrucción para el agente, es solo una conveniencia para nosotros. La denominación hace que el código (en este punto) sea más fácil de leer y más fácil de cambiar.

       #define counter m[30]   // name a memory location
       mov 1000 counter
    loop:                      // name a instruction pointer location
        sub counter 1
        (if not-zero) jmp-to loop  
    

11. Subrutina de un nivel : suponga que hay una serie de pasos que debe ejecutar con frecuencia. Puede almacenar los pasos en una posición con nombre en la memoria y luego saltar a esa posición cuando necesite ejecutarlos (llamada). Al final de la secuencia, deberá volver al punto de llamada para continuar la ejecución. Con este mecanismo, está creando nuevas instrucciones (subrutinas) al componer las instrucciones principales.

    Implementación: (no se requieren nuevos conceptos)

    • Almacene el puntero de instrucción actual en una posición de memoria predefinida
    • saltar a la subrutina
    • al final de la subrutina, recupera el puntero de instrucción de la ubicación de memoria predefinida, saltando efectivamente a la siguiente instrucción de la llamada original

    Problema con el nivel uno implementación de : no puede llamar a otra subrutina desde una subrutina. Si lo hace, sobrescribirá la dirección de retorno (variable global), por lo que no puede anidar llamadas.

    Para tener una mejor implementación de subrutinas: necesita un STACK

12. Pila : define un espacio de memoria para que funcione como una "pila", puede "insertar" valores en la pila y también "extraer" el último valor "insertado". Para implementar una pila, necesitará un puntero de pila (similar al puntero de instrucciones) que apunta a la "cabeza" real de la pila. Cuando "empuja" un valor, el puntero de la pila disminuye y almacena el valor. Cuando hace “pop”, obtiene el valor en el Stack Pointer real y luego el Stack Pointer se incrementa.

13. Subrutinas Ahora que tenemos una pila , podemos implementar subrutinas adecuadas que permitan llamadas anidadas . La implementación es similar, pero en lugar de almacenar el puntero de instrucción en una posición de memoria predefinida, "empujamos" el valor de la IP en la pila . Al final de la subrutina, simplemente "sacamos" el valor de la pila, volviendo a la instrucción después de la llamada original . Esta implementación, tener una "pila" permite llamar a una subrutina desde otra subrutina. Con esta implementación, podemos crear varios niveles de abstracción al definir nuevas instrucciones como subrutinas, utilizando instrucciones centrales u otras subrutinas como bloques de construcción.

14. Recursión : ¿Qué sucede cuando una subrutina se llama a sí misma? Esto se llama "recursión".

    Problema: sobrescribir los resultados intermedios locales que una subrutina puede estar almacenando en la memoria. Como está llamando / reutilizando los mismos pasos, si el resultado intermedio se almacena en ubicaciones de memoria predefinidas (variables globales), se sobrescribirán en las llamadas anidadas.

    Solución: para permitir la recursividad, las subrutinas deben almacenar resultados intermedios locales en la pila , por lo tanto, en cada llamada recursiva (directa o indirecta) los resultados intermedios se almacenan en diferentes ubicaciones de memoria.

...

Habiendo alcanzado la recursión, nos detenemos aquí.

Conclusión:

En una arquitectura de Von Neumann, claramente "Iteración" es un concepto más simple / básico que "Recursión" . Tenemos una forma de "Iteración" en el nivel 7, mientras que "Recursión" está en el nivel 14 de la jerarquía de conceptos.

La iteración siempre será más rápida en el código de máquina porque implica menos instrucciones, por lo tanto, menos ciclos de CPU.

Cuál es mejor"?

• Debe usar "iteración" cuando procesa estructuras de datos simples y secuenciales, y en todas partes lo hará un "bucle simple".

• Debe usar "recursividad" cuando necesite procesar una estructura de datos recursiva (me gusta llamarlas "Estructuras de datos fractales"), o cuando la solución recursiva es claramente más "elegante".

Consejo : use la mejor herramienta para el trabajo, pero comprenda el funcionamiento interno de cada herramienta para elegir sabiamente.

Finalmente, tenga en cuenta que tiene muchas oportunidades para usar la recursividad. Tienes estructuras de datos recursivas en todas partes, estás viendo una ahora: partes del DOM que respaldan lo que estás leyendo son un RDS, una expresión JSON es un RDS, el sistema de archivos jerárquico en tu computadora es un RDS, es decir: tienes un directorio raíz, que contiene archivos y directorios, cada directorio que contiene archivos y directorios, cada uno de esos directorios que contiene archivos y directorios ...

La recursión puede ser más rápida cuando la alternativa es administrar explícitamente una pila, como en los algoritmos de clasificación o de árbol binario que menciona.

He tenido un caso en el que reescribir un algoritmo recursivo en Java lo hizo más lento.

Por lo tanto, el enfoque correcto es escribirlo primero de la manera más natural, solo optimizar si el perfil muestra que es crítico, y luego medir la supuesta mejora.

La recursión de la cola es tan rápida como el bucle. Muchos lenguajes funcionales tienen una recursión de cola implementada en ellos.

Considere lo que debe hacerse absolutamente para cada iteración y recursión.

• iteración: un salto al comienzo del bucle
• recursividad: un salto al comienzo de la función llamada

Usted ve que no hay mucho espacio para las diferencias aquí.

(Supongo que la recursión es una llamada de cola y el compilador es consciente de esa optimización).

La mayoría de las respuestas aquí olvidan al culpable obvio de por qué la recursión es a menudo más lenta que las soluciones iterativas. Está vinculado con la construcción y desmontaje de los marcos de pila, pero no es exactamente eso. Generalmente es una gran diferencia en el almacenamiento de la variable automática para cada recursión. En un algoritmo iterativo con un bucle, las variables a menudo se mantienen en registros e incluso si se derraman, residirán en el caché de Nivel 1. En un algoritmo recursivo, todos los estados intermedios de la variable se almacenan en la pila, lo que significa que generarán muchos más derrames en la memoria. Esto significa que incluso si realiza la misma cantidad de operaciones, tendrá muchos accesos de memoria en el bucle activo y, lo que es peor, estas operaciones de memoria tienen una tasa de reutilización pésima que hace que las memorias caché sean menos efectivas.

Los algoritmos recursivos TL; DR generalmente tienen un comportamiento de caché peor que los iterativos.

La mayoría de las respuestas aquí son incorrectas . La respuesta correcta es que depende . Por ejemplo, aquí hay dos funciones C que recorren un árbol. Primero el recursivo:

static
void mm_scan_black(mm_rc *m, ptr p) {
    SET_COL(p, COL_BLACK);
    P_FOR_EACH_CHILD(p, {
        INC_RC(p_child);
        if (GET_COL(p_child) != COL_BLACK) {
            mm_scan_black(m, p_child);
        }
    });
}

Y aquí está la misma función implementada usando iteración:

static
void mm_scan_black(mm_rc *m, ptr p) {
    stack *st = m->black_stack;
    SET_COL(p, COL_BLACK);
    st_push(st, p);
    while (st->used != 0) {
        p = st_pop(st);
        P_FOR_EACH_CHILD(p, {
            INC_RC(p_child);
            if (GET_COL(p_child) != COL_BLACK) {
                SET_COL(p_child, COL_BLACK);
                st_push(st, p_child);
            }
        });
    }
}

No es importante comprender los detalles del código. Solo eso pson nodos y eso P_FOR_EACH_CHILDes lo que hace caminar. En la versión iterativa necesitamos una pila explícitast en la que se empujan los nodos y luego se extraen y se manipulan.

La función recursiva se ejecuta mucho más rápido que la iterativa. La razón es porque en este último, para cada elemento, se necesita una CALLpara la función st_pushy luego otra parast_pop .

En el primero, solo tienes el recursivo CALL para cada nodo.

Además, acceder a variables en la pila de llamadas es increíblemente rápido. Significa que está leyendo de la memoria, que probablemente siempre esté en el caché más interno. Una pila explícita, por otro lado, debe ser respaldada pormalloc : memoria ed del montón, que es mucho más lenta de acceder.

Con una cuidadosa optimización, como la alineación st_pushyst_pop , puedo alcanzar aproximadamente la paridad con el enfoque recursivo. Pero al menos en mi computadora, el costo de acceder a la memoria de almacenamiento dinámico es mayor que el costo de la llamada recursiva.

Pero esta discusión es principalmente discutible porque la caminata recursiva es incorrecta . Si tiene un árbol lo suficientemente grande, se quedará sin espacio de pila de llamadas, por lo que debe usarse un algoritmo iterativo.

En general, no, la recursión no será más rápida que un bucle en cualquier uso realista que tenga implementaciones viables en ambas formas. Quiero decir, claro, podrías codificar los bucles que demoran una eternidad, pero habría mejores formas de implementar el mismo bucle que podría superar cualquier implementación del mismo problema a través de la recursividad.

Golpeaste el clavo en la cabeza con respecto a la razón; crear y destruir marcos de pila es más costoso que un simple salto.

Sin embargo, tenga en cuenta que dije "tiene implementaciones viables en ambas formas". Para cosas como muchos algoritmos de clasificación, tiende a no existir una forma muy viable de implementarlos que no configure de manera efectiva su propia versión de una pila, debido a la generación de "tareas" secundarias que son inherentemente parte del proceso. Por lo tanto, la recursión puede ser tan rápida como intentar implementar el algoritmo a través del bucle.

Editar: esta respuesta supone lenguajes no funcionales, donde la mayoría de los tipos de datos básicos son mutables. No se aplica a lenguajes funcionales.

En cualquier sistema realista, no, crear un marco de pila siempre será más costoso que un INC y un JMP. Es por eso que los compiladores realmente buenos transforman automáticamente la recursividad de cola en una llamada al mismo marco, es decir, sin la sobrecarga, para que obtenga la versión fuente más legible y la versión compilada más eficiente. Un compilador realmente muy bueno debería incluso ser capaz de transformar la recursividad normal en una recursividad de cola donde sea posible.

La programación funcional tiene más que ver con " qué " que con " cómo ".

Los implementadores del lenguaje encontrarán una manera de optimizar el funcionamiento del código debajo, si no intentamos hacerlo más optimizado de lo que debería ser. La recursión también se puede optimizar dentro de los idiomas que admiten la optimización de llamadas de cola.

Lo que más importa desde el punto de vista del programador es la legibilidad y la facilidad de mantenimiento en lugar de la optimización en primer lugar. Nuevamente, "la optimización prematura es la raíz de todo mal".

Esto es una suposición. En general, la recursión probablemente no supera el bucle a menudo o nunca en problemas de tamaño decente si ambos usan algoritmos realmente buenos (sin contar la dificultad de implementación), puede ser diferente si se usa con un lenguaje con recursividad de llamada de cola (y un algoritmo recursivo de cola y con bucles también como parte del lenguaje), que probablemente tendría una similitud muy parecida y posiblemente incluso preferiría la recursión algunas veces.

Según la teoría, son las mismas cosas. La recursión y el bucle con la misma complejidad O () funcionarán con la misma velocidad teórica, pero, por supuesto, la velocidad real depende del lenguaje, el compilador y el procesador. El ejemplo con potencia de número se puede codificar de forma iterativa con O (ln (n)):

  int power(int t, int k) {
  int res = 1;
  while (k) {
    if (k & 1) res *= t;
    t *= t;
    k >>= 1;
  }
  return res;
  }