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

286

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.

Carson Myers
fuente
3
A veces, el procedimiento iterativo o las fórmulas de forma cerrada para algunas recurrencias tardan siglos en aparecer. Creo que solo en esos momentos la recursividad es más rápida :) lol
Pratik Deoghare
24
Hablando por mí mismo, prefiero la iteración. ;-)
Iterator
posible duplicado de recursión o iteración?
nawfal
@PratikDeoghare No, la pregunta no se trata de elegir un algoritmo completamente diferente. Siempre puede convertir una función recursiva en un método de funcionamiento idéntico que use un bucle. Por ejemplo, esta respuesta tiene el mismo algoritmo tanto en formato recursivo como en bucle . En general, colocará una tupla de los argumentos de la función recursiva en una pila, empujando a la pila para llamar, descartando de la pila para regresar de la función.
TamaMcGlinn

Respuestas:

356

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.

Dietrich Epp
fuente
48
I +1 eso, y me gustaría comentar que "recursión" y "bucles" son justo lo que los humanos llaman su código. Lo importante para el rendimiento no es cómo se nombran las cosas, sino cómo se compilan / interpretan. La recursión, por definición, es un concepto matemático y tiene poco que ver con los marcos de la pila y las cosas de ensamblaje.
P Shved
1
Además, la recursión es, en general, el enfoque más natural en lenguajes funcionales, y la iteración es normalmente más intuitiva en lenguajes imperativos. Es improbable que la diferencia de rendimiento sea notable, así que solo usa lo que se sienta más natural para ese idioma en particular. Por ejemplo, es probable que no desee utilizar la iteración en Haskell cuando la recursividad es mucho más simple.
Sasha Chedygov
44
En general, la recursión se compila en bucles, siendo los bucles una construcción de nivel inferior. ¿Por qué? Debido a que la recursividad generalmente está bien fundada sobre alguna estructura de datos, induce un álgebra F inicial y le permite probar algunas propiedades sobre la terminación junto con argumentos inductivos sobre la estructura del cálculo (recursivo). El proceso por el cual se compila la recursividad en bucles es la optimización de la llamada de cola.
Kristopher Micinski
Lo que más importa son las operaciones no realizadas. Cuanto más "IO", más tiene que procesar. Los datos de Un-IOing (también conocidos como indexación) son siempre el mayor impulso de rendimiento para cualquier sistema porque no tiene que procesarlos en primer lugar.
Jeff Fischer
53

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

Lucio M. Tato
fuente
2
Está asumiendo que su progresión es 1) necesaria y 2) que se detiene allí donde lo hizo. Pero 1) no es necesario (por ejemplo, la recursión puede convertirse en un salto, como explica la respuesta aceptada, por lo que no se necesita apilar), y 2) no tiene que detenerse allí (por ejemplo, eventualmente Alcanzará el procesamiento concurrente, que puede necesitar bloqueos si tiene un estado mutable como lo introdujo en su segundo paso, por lo que todo se ralentiza; mientras que una solución inmutable como una funcional / recursiva evitaría el bloqueo, por lo que podría ser más rápido / más paralelo) .
hmijail llora a los despedidos
2
"La recursión puede convertirse en un salto" es falsa. La recursión verdaderamente útil no puede convertirse en un salto. La llamada de cola "recursión" es un caso especial, donde codifica "como recursión" algo que el compilador puede simplificar en un bucle. También estás combinando "inmutable" con "recursión", esos son conceptos ortogonales.
Lucio M. Tato
"La recursión verdaderamente útil no se puede convertir en un salto" -> ¿entonces la optimización de la cola de llamadas es de alguna manera inútil? Además, la inmutable y la recursión pueden ser ortogonales, pero usted vincula el bucle con contadores mutables. Mire su paso 9. Me parece que está pensando que el bucle y la recursión son conceptos radicalmente diferentes; ellos no lo son. stackoverflow.com/questions/2651112/…
hmijail llora a los resigneados el
@hmijail Creo que una palabra mejor que "útil" es "verdadero". La recursividad de la cola no es verdadera porque solo usa la sintaxis de llamada de función para disfrazar la ramificación incondicional, es decir, la iteración. La verdadera recursión nos proporciona una pila de retroceso. Sin embargo, la recursividad de la cola sigue siendo expresiva, lo que la hace útil. Las propiedades de recursividad que facilitan o facilitan el análisis de la corrección del código se confieren al código iterativo cuando se expresa mediante llamadas de cola. Aunque eso a veces se ve ligeramente compensado por complicaciones adicionales en la versión de cola como parámetros adicionales.
Kaz
34

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.

starblue
fuente
2
+1 para " primero escríbalo de la manera más natural " y especialmente " solo optimice si el perfil muestra que es crítico "
TripeHound
2
+1 por reconocer que la pila de hardware puede ser más rápida que un software, implementado manualmente, en la pila del montón. Mostrando efectivamente que todas las respuestas "no" son incorrectas.
sh1
12

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

Pasi Savolainen
fuente
9

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.

Patrick Schlüter
fuente
6

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.

Björn Lindqvist
fuente
Puedo confirmar que me he encontrado con una situación similar y que hay situaciones en las que la recursión puede ser más rápida que una pila manual en el montón. Especialmente cuando la optimización está activada en el compilador para evitar parte de la sobrecarga de llamar a una función.
while1fork
1
Hice un recorrido de pre-pedido de un árbol binario de 7 nodos 10 ^ 8 veces. Recursión 25ns. Pila explícita (comprobada o no, no hace mucha diferencia) ~ 15ns. La recursión debe hacer más (guardar y restaurar registros + (generalmente) alineaciones de cuadro más estrictas) además de simplemente empujar y saltar. (Y empeora con PLT en bibliotecas vinculadas dinámicamente). No es necesario asignar de forma dinámica la pila explícita. Puede hacer un obstáculo cuyo primer cuadro está en la pila de llamadas regular para no sacrificar la localidad de caché para el caso más común en el que no excede el primer bloque.
PSkocik
3

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.

Ámbar
fuente
Esa es también la razón por la cual los compiladores optimizan a menudo varios casos de recursividad en idiomas donde la recursión se usa con frecuencia. En F #, por ejemplo, además del soporte total para las funciones recursivas de cola con el código de operación .tail, a menudo se ve una función recursiva compilada como un bucle.
em70
Sí. La recursividad de la cola a veces puede ser lo mejor de ambos mundos: la forma funcionalmente "apropiada" de implementar una tarea recursiva y el rendimiento del uso de un bucle.
Ámbar
1
Esto no es, en general, correcto. En algunos entornos, la mutación (que interactúa con GC) es más costosa que la recursión de cola, que se transforma en un bucle más simple en la salida que no utiliza un marco de pila adicional.
Dietrich Epp
2

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.

Kilian Foth
fuente
1

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

noego
fuente
0

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.

Roman A. Taycher
fuente
0

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;
  }
Hydrophis Spiralis
fuente
1
Big O es "proporcional a". Ambos son O(n), pero uno puede tomar xmás tiempo que el otro, para todos n.
ctrl-alt-delor