performance - resueltos - recursividad javascript ejemplos

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

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

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

Explicación:

Si construye las operaciones mínimas de una computadora genérica desde cero, "Iteración" aparece primero como bloque de construcción y requiere menos recursos que la "recursión", ergo es más rápido.

Construyendo una máquina de pseudo-computación desde cero:

Pregúntese : ¿Qué necesita para calcular un valor, es decir, 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 básicos, luego construiremos conceptos de segundo nivel con esos, y así sucesivamente.

Primer concepto: Células 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", llamada Memoria , M [0..Infinito].
Instrucciones: hacer algo - transformar una celda, cambiar su valor. alterar estado Cada instrucción interesante realiza una transformación. Las instrucciones básicas son:
a) Establecer y mover celdas de memoria
- almacenar un valor en la memoria, por ejemplo: almacenar 5 m [4]
- copie un valor a otra posición: por ejemplo: almacenar m [4] m [8]
b) Lógica y aritmética.
- y, o, xor, no
- añadir, sub, mul, div. por ejemplo, agregue m [7] m [8]
Un agente de ejecución : un núcleo en una CPU moderna. Un "agente" es algo que puede ejecutar instrucciones. Un agente también puede ser una persona siguiendo el algoritmo en papel.
Orden de los pasos: una secuencia de instrucciones : es decir: haga esto primero, haga 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, 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)
Así que incluso las expresiones de infijo, ya que tienes un orden específico de evaluación, son una secuencia imperativa de instrucciones . La expresión implica una secuencia de operaciones que deben realizarse en un orden específico, y debido a que hay pasos , también hay una variable intermedia implícita de "resultado".
Indicador de instrucción : si tiene una secuencia de pasos, también tiene un "indicador de instrucción" implícito. El puntero de instrucción marca la siguiente instrucción y avanza después de que se lee la instrucción pero antes de que se ejecute la instrucción.
En esta máquina de pseudo-computación, el puntero de instrucciones es 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 (incluidos los registros) forman parte de la "Memoria")
Salto : 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 la instrucción de la tienda con un nuevo nombre: Jump . Usamos un nuevo nombre porque es más fácil de pensar como un nuevo concepto. Al modificar el puntero de instrucciones, le indicamos al agente que "vaya al paso x".
Iteración infinita : saltando hacia atrás, ahora puede hacer que el agente "repita" un cierto número de pasos. En este punto tenemos infinita iteración.
1. mov 1000 m[30] 2. sub m[30] 1 3. jmp-to 2 // infinite loop
Condicional - Ejecución condicional de instrucciones. Con la cláusula "condicional", puede ejecutar condicionalmente una o varias instrucciones basadas en el estado actual (que se puede configurar con una instrucción previa).
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 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.
Nombrar : dar nombres a una ubicación de memoria específica que contiene datos o que contiene un paso . Esto es solo una "conveniencia" de tener. No agregamos nuevas instrucciones al tener la capacidad de definir "nombres" para las ubicaciones de memoria. "Nombrar" no es una instrucción para el agente, es solo una conveniencia para nosotros. El nombre 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
Subrutina de un nivel : suponga que hay una serie de pasos que necesita 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 con la ejecución. Con este mecanismo, está creando nuevas instrucciones (subrutinas) al componer las instrucciones básicas.
Implementación: (no se requieren nuevos conceptos)
- Almacene el puntero de instrucciones actual en una posición de memoria predefinida
- saltar a la subrutina
- al final de la subrutina, recupera el puntero de instrucciones de la ubicación de memoria predefinida, saltando efectivamente a la siguiente instrucción de la llamada original
Problema con la implementación de un nivel : No puede llamar a otra subrutina desde una subrutina. Si lo hace, sobrescribirá la dirección de retorno (variable global), por lo que no podrá anidar llamadas.
Para tener una mejor implementación para las subrutinas: necesitas un STACK
Pila : define un espacio de memoria para trabajar como una "pila", puede "empujar" los valores en la pila y también "hacer estallar" el último valor "empujado". Para implementar una pila, necesitará un puntero de pila (similar al puntero de instrucciones) que apunta a la "cabeza" real de la pila. Cuando usted "presiona" un valor, el puntero de pila disminuye y usted almacena el valor. Cuando “aparece”, obtiene el valor en el puntero de pila real y luego se incrementa el puntero de pila.
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 instrucciones en una posición de memoria predefinida, "presionamos" el valor de la IP en la pila . Al final de la subrutina, simplemente "extraemos" el valor de la pila, volviendo a la instrucción después de la llamada original. Esta implementación, al 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 básicas u otras subrutinas como bloques de construcción.
Recursión : ¿Qué sucede cuando una subrutina se llama a sí misma? Esto se llama "recursión".
Problema: sobrescribiendo los resultados intermedios locales que una subrutina puede almacenar en la memoria. Dado que 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 recursión, 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 llegado a la recursión paramos 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 la máquina porque implica menos instrucciones, por lo tanto, menos ciclos de CPU.

Cuál es mejor"?

Debería usar la "iteración" cuando procesa estructuras de datos simples y secuenciales, y en todas partes funcionará un "bucle simple".
Debe usar "recursividad" cuando necesite procesar una estructura de datos recursiva (me gusta llamarlos "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 poder elegir sabiamente.

Finalmente, tenga en cuenta que tiene muchas oportunidades para usar la recursión. Tiene estructuras de datos recursivos en todas partes, ahora está viendo una: las partes del DOM que admiten lo que está leyendo son un RDS, una expresión JSON es un RDS, el sistema de archivos jerárquico en su computadora es un RDS, es decir: tiene un directorio raíz, que contiene archivos y directorios, cada directorio que contiene archivos y directorios, cada uno de esos directorios que contienen archivos y directorios ...

Sé que la recursión es a veces mucho más limpia que el bucle, y no pregunto 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: ¿es la recursión cada vez más rápida que un bucle? A mi parecer, siempre sería capaz de refinar un bucle y lograr que se ejecute más rápidamente que una función recursiva, ya que el bucle está ausente constantemente configurando nuevos marcos de pila.

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

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

iteración: un salto al principio del bucle
recursión: un salto al principio 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).

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 recursión de la cola en una llamada al mismo marco, es decir, sin la sobrecarga, para obtener la versión fuente más legible y la versión compilada más eficiente. Un compilador realmente bueno debería incluso ser capaz de transformar la recursión normal en una recursión de la cola donde sea posible.

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ía codificar bucles que tardan una eternidad, pero habría mejores formas de implementar el mismo bucle que podría superar a cualquier implementación del mismo problema a través de la recursión.

Se golpea 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 que "tiene implementaciones viables en ambas formas". Para cosas como muchos algoritmos de clasificación, tiende a no haber una forma muy viable de implementarlos que no configure efectivamente su propia versión de una pila, debido al desarrollo 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.

Edición: esta respuesta está asumiendo lenguajes no funcionales, donde la mayoría de los tipos de datos básicos son mutables. No se aplica a lenguajes funcionales.

Esto depende del idioma que se utilice. Usted escribió ''lenguaje-agnóstico'', así que daré algunos ejemplos.

En Java, C y Python, la recursión es bastante costosa 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, la recursión se transforma en un salto simple, pero cambiar la variable de bucle (que es mutable) a veces requiere algunas operaciones relativamente pesadas, especialmente en implementaciones que admiten múltiples subprocesos 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 se ejecutan al mismo tiempo.

Sé que en algunas implementaciones de Esquemas, 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 recursión 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 darán como resultado que se genere el mismo ensamblaje (colóquelo en su tubería y hágalo humo).

Addendum: en algunos entornos, la mejor alternativa no es la recursión ni la iteración, sino las funciones de orden superior. Estos incluyen "mapa", "filtro" y "reducir" (que también se denomina "pliegue"). 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 las únicas) que obtienen un impulso de la paralelización automática, por lo que pueden ser mucho más rápidas que la iteración o la recursión. Data Parallel Haskell es un ejemplo de dicho entorno.

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

Esto es una conjetura. En general, la recursión probablemente no se repite con frecuencia o nunca en problemas de tamaño decente si ambos utilizan algoritmos realmente buenos (sin tener en cuenta la dificultad de la implementación), puede ser diferente si se usa con un lenguaje con recursión de llamada de cola (y un algoritmo recursivo de cola) y con los bucles también como parte del lenguaje), que probablemente tendrían una similitud muy similar y posiblemente incluso una parte de la recursión.

La mayoría de las respuestas aquí están equivocadas . La respuesta correcta es que depende . Por ejemplo, aquí hay dos funciones C que caminan a través de 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 entender los detalles del código. Solo que p son nodos y que P_FOR_EACH_CHILD camina. En la versión iterativa, necesitamos un st pila explícito en el que los nodos se empujan y luego se revientan y manipulan.

La función recursiva se ejecuta mucho más rápido que la iterativa. El motivo es que en este último, para cada elemento, se necesita una CALL a la función st_push y luego otra a st_pop .

En el primero, solo tiene la CALL recursiva para cada nodo.

Además, acceder a las variables en la pila de llamadas es increíblemente rápido. Significa que está leyendo de la memoria, que es probable que siempre esté en el caché más interno. Una pila explícita, por otro lado, tiene que estar respaldada por la memoria malloc : ed de la pila, que es mucho más lenta de acceder.

Con una optimización cuidadosa, como la st_push y st_pop , puedo alcanzar aproximadamente la paridad con el enfoque recursivo. Pero al menos en mi computadora, el costo de acceder a la memoria del montón es mayor que el costo de la llamada recursiva.

Pero esta discusión es sobre todo discutible porque la caminata recursiva del árbol 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.

La mayoría de las respuestas aquí olvidan el culpable obvio de por qué la recursión suele ser más lenta que las soluciones iterativas. Está vinculado con la acumulación y el desmontaje de los marcos de pila, pero no es exactamente eso. En general, 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 engendrará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 circuito activo y, lo que es peor, estas operaciones de memoria tienen una tasa de reutilización pésima, lo que hace que las cachés sean menos efectivas.

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

La programación funcional es más acerca de " qué " en lugar de " cómo ".

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

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

La recursión puede ser más rápida donde 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 donde reescribir un algoritmo recursivo en Java lo hizo más lento.

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

Según la teoría es lo mismo. 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 idioma, el compilador y el procesador. El ejemplo con potencia de número se puede codificar de manera 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; }

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