¿Por qué los bucles son más rápidos que la recursividad?

En la práctica, entiendo que cualquier recursión puede escribirse como un bucle (y viceversa (?)) Y si medimos con computadoras reales, encontramos que los bucles son más rápidos que la recursividad para el mismo problema. Pero, ¿hay alguna teoría que haga esta diferencia o es principalmente empírica?

La razón por la que los bucles son más rápidos que la recursividad es fácil.
Un bucle se ve así en el ensamblaje.

mov loopcounter,i
dowork:/do work
dec loopcounter
jmp_if_not_zero dowork

Un solo salto condicional y algo de contabilidad para el contador de bucles.

La recursividad (cuando no es o no puede ser optimizada por el compilador) se ve así:

start_subroutine:
pop parameter1
pop parameter2
dowork://dowork
test something
jmp_if_true done
push parameter1
push parameter2
call start_subroutine
done:ret

Es mucho más complejo y obtienes al menos 3 saltos (1 prueba para ver si se realizó, una llamada y una devolución).
También en la recursión, los parámetros deben configurarse y recuperarse.
No se necesita nada de esto en un bucle porque todos los parámetros ya están configurados.

Teóricamente, los parámetros también podrían permanecer en su lugar con la recursividad, pero ningún compilador que conozco realmente llega tan lejos en su optimización.

Diferencias entre una llamada y un jmp
Un par de devolución de llamada no es mucho más caro que el jmp. El par toma 2 ciclos y el jmp toma 1; apenas perceptible
Al llamar a las convenciones que admiten parámetros de registro, la sobrecarga de los parámetros es mínima, pero incluso los parámetros de pila son baratos siempre que los búferes de la CPU no se desborden .
Es la sobrecarga de la configuración de la llamada dictada por la convención de llamada y el manejo de parámetros en uso lo que ralentiza la recursividad.
Esto depende mucho de la implementación.

Ejemplo de manejo de recursividad deficiente Por ejemplo, si se pasa un parámetro que se cuenta como referencia (por ejemplo, un parámetro de tipo administrado sin constante) agregará 100 ciclos haciendo un ajuste bloqueado del recuento de referencia, matando totalmente el rendimiento frente a un bucle.
En los idiomas que están ajustados a la recursividad, este mal comportamiento no ocurre.

Optimización de la CPU
La otra razón por la cual la recursividad es más lenta es que funciona contra los mecanismos de optimización en las CPU.
Las devoluciones solo se pueden predecir correctamente si no hay demasiadas en una fila. La CPU tiene un búfer de retorno de pila con unos (pocos) puñados de entradas. Una vez que se agoten, cada retorno adicional se predecirá erróneamente, lo que provocará enormes demoras.
En cualquier CPU que utilice una memoria de retorno de pila basada en una recursión que exceda el tamaño del búfer, es mejor evitarla.

Acerca de los ejemplos de código trivial que usan la recursión
Si usa un ejemplo trivial de recursión como la generación de números de Fibonacci, entonces estos efectos no ocurren, porque cualquier compilador que 'sepa' sobre la recursión la transformará en un bucle, al igual que cualquier programador que valga la pena. haría.
Si ejecuta estos ejemplos triviales en un entorno que no se optimiza correctamente, la pila de llamadas (innecesariamente) crecerá fuera de los límites.

Acerca de la recursividad de cola
Tenga en cuenta que a veces el compilador optimiza la recursión de cola cambiándola a un bucle. Es mejor confiar solo en este comportamiento en idiomas que tengan un buen historial conocido en este sentido.
Muchos idiomas insertan código de limpieza oculto antes del retorno final, lo que impide la optimización de la recursión de cola.

Confusión entre verdadera y pseudo recursividad
Si su entorno de programación convierte su código fuente recursivo en un bucle, entonces posiblemente no se trate de una verdadera recursión que se está ejecutando.
La verdadera recursión requiere una reserva de migas de pan, de modo que la rutina recursiva pueda rastrear sus pasos después de salir.
Es el manejo de este sendero lo que hace que la recursión sea más lenta que usar un bucle. Este efecto se magnifica con las implementaciones actuales de la CPU como se describe anteriormente.

Efecto del entorno de programación
Si su lenguaje está optimizado para la optimización de la recursividad, entonces siga adelante y use la recursividad en cada oportunidad. En la mayoría de los casos, el lenguaje convertirá su recursión en una especie de bucle.
En aquellos casos en que no puede, el programador también se vería en apuros. Si su lenguaje de programación no está ajustado a la recursividad, entonces debe evitarse a menos que el dominio sea adecuado para la recursividad.
Desafortunadamente, muchos idiomas no manejan bien la recursividad.

Uso indebido de la recursión
No es necesario calcular la secuencia de Fibonacci utilizando la recursión, de hecho, es un ejemplo patológico.
La recursión se utiliza mejor en lenguajes que la admiten explícitamente o en dominios donde la recursividad brilla, como el manejo de datos almacenados en un árbol.

Entiendo que cualquier recursión puede escribirse como un bucle

Sí, si está dispuesto a poner el carro delante del caballo.
Todas las instancias de recursión pueden escribirse como un bucle, algunas de esas instancias requieren que use una pila explícita como almacenamiento.
Si necesita rodar su propia pila solo para convertir el código recursivo en un bucle, también podría usar la recursión simple.
A menos que, por supuesto, tenga necesidades especiales, como usar enumeradores en una estructura de árbol y no tenga el soporte de lenguaje adecuado.

Estas otras respuestas son algo engañosas. Estoy de acuerdo en que establecen detalles de implementación que pueden explicar esta disparidad, pero exageran el caso. Como sugiere correctamente jmite, están orientados a la implementación hacia implementaciones rotas de llamadas a funciones / recursividad. Muchos idiomas implementan bucles por recursión, por lo que los bucles claramente no serán más rápidos en esos idiomas. La recursión no es menos eficiente que el bucle (cuando ambos son aplicables) en teoría. Permítanme citar el resumen del artículo de Guy Steele de 1977 que desacredita el mito de la "Llamada de procedimiento costoso" o las implementaciones de procedimientos consideradas dañinas o Lambda: el último GOTO

El folklore afirma que las declaraciones GOTO son "baratas", mientras que las llamadas a procedimientos son "caras". Este mito es en gran parte el resultado de implementaciones de lenguaje mal diseñadas. Se considera el crecimiento histórico de este mito. Se discuten ideas teóricas y una implementación existente que desacredita este mito. Se muestra que el uso irrestricto de llamadas a procedimientos permite una gran libertad estilística. En particular, cualquier diagrama de flujo puede escribirse como un programa "estructurado" sin introducir variables adicionales. La dificultad con la declaración GOTO y la llamada al procedimiento se caracteriza por un conflicto entre conceptos de programación abstractos y construcciones de lenguaje concretas.

El "conflicto entre los conceptos de programación abstractos y las construcciones de lenguaje concreto" puede verse en el hecho de que la mayoría de los modelos teóricos de, por ejemplo, el cálculo lambda sin tipo , no tienen una pila . Por supuesto, este conflicto no es necesario como lo ilustra el artículo anterior y también lo demuestran los lenguajes que no tienen un mecanismo de iteración que no sea la recursión como Haskell.

fixfix f x = f (fix f) x$(\lambda x.M)N \leadsto M[N/x]$$[N/x]$$x$$M$$N$$\leadsto$

Ahora por un ejemplo. Definir factcomo

fact = fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1

Aquí está la evaluación de fact 3, donde, por compacidad, usaré gcomo sinónimo de fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)), es decir fact = g 1. Esto no afecta mi argumento.

fact 3 
~> g 1 3
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1 3 
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 1 3
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 1 3
~> (λn.if n == 0 then 1 else g (1*n) (n-1)) 3
~> if 3 == 0 then 1 else g (1*3) (3-1)
~> g (1*3) (3-1)
~> g 3 2
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 3 2
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 3 2
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 3 2
~> (λn.if n == 0 then 3 else g (3*n) (n-1)) 2
~> if 2 == 0 then 3 else g (3*2) (2-1)
~> g (3*2) (2-1)
~> g 6 1
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 1
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 1
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 1
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 1
~> if 1 == 0 then 6 else g (6*1) (1-1)
~> g (6*1) (1-1)
~> g 6 0
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 0
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 0
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 0
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 0
~> if 0 == 0 then 6 else g (6*0) (0-1)
~> 6

Puede ver desde la forma sin siquiera mirar los detalles que no hay crecimiento y que cada iteración necesita la misma cantidad de espacio. (Técnicamente, el resultado numérico crece, lo que es inevitable e igual de cierto para un whilebucle). Te desafío a que señales aquí la "pila" de crecimiento ilimitado.

Parece que la semántica arquetípica del cálculo lambda ya hace lo que comúnmente se denomina mal "optimización de llamada de cola". Por supuesto, no hay "optimización" aquí. Aquí no hay reglas especiales para las llamadas "de cola" en lugar de las llamadas "normales". Por esta razón, es difícil dar una caracterización "abstracta" de lo que está haciendo la "optimización" de la llamada de cola, ya que en muchas caracterizaciones abstractas de la semántica de llamadas de función, ¡no hay nada que hacer para la "optimización" de la llamada de cola!

Que la definición análoga de fact"desbordamientos de pila" en muchos idiomas, es un fracaso por parte de esos idiomas para implementar correctamente la semántica de llamadas de función. (Algunos idiomas tienen una excusa). La situación es más o menos análoga a tener una implementación de lenguaje que implementara matrices con listas vinculadas. La indexación en tales "matrices" sería una operación O (n) que no cumple con las expectativas de las matrices. Si hiciera una implementación por separado del lenguaje, que usara matrices reales en lugar de listas vinculadas, no diría que he implementado la "optimización de acceso a matrices", diría que arreglé una implementación rota de matrices.

Entonces, respondiendo a la respuesta de Veedrac. Las pilas no son "fundamentales" para la recursión . En la medida en que se produzca un comportamiento "similar a la pila" durante el curso de la evaluación, esto solo puede suceder en los casos en que los bucles (sin una estructura de datos auxiliar) no serían aplicables en primer lugar. Para decirlo de otra manera, puedo implementar bucles con recursividad con exactamente las mismas características de rendimiento. De hecho, Scheme y SML contienen construcciones en bucle, pero ambas definen esas en términos de recursión (y, al menos en Scheme, a domenudo se implementa como una macro que se expande en llamadas recursivas). Del mismo modo, para la respuesta de Johan, nada dice un El compilador debe emitir el ensamblado que Johan describió para la recursividad. En efecto,exactamente lo mismo ensamblaje si usa bucles o recursividad. La única vez que el compilador sería (de alguna manera) obligado para emitir ensamblaje como lo que describe Johan es cuando estás haciendo algo que no es expresable por un bucle de todos modos. Como se describe en el documento de Steele y se demuestra por la práctica real de idiomas como Haskell, Scheme y SML, no es "extremadamente raro" que las llamadas de cola se puedan "optimizar", siempre pueden pueden "optimizar". Si un uso particular de la recursión se ejecutará en un espacio constante depende de cómo se escriba, pero las restricciones que debe aplicar para que sea posible son las restricciones que necesitaría para adaptar su problema a la forma de un bucle. (En realidad, son menos estrictos. Hay problemas, como la codificación de máquinas de estado, que se manejan de manera más limpia y eficiente a través de llamadas de cola en lugar de bucles que requerirían variables auxiliares). De nuevo, requiere hacer más trabajo es cuando tu código no es un bucle de todos modos.

Supongo que Johan se está refiriendo a los compiladores de C que tienen restricciones arbitrarias sobre cuándo realizará la "optimización" de la cola. Es probable que Johan también se refiera a lenguajes como C ++ y Rust cuando habla de "lenguajes con tipos administrados". El lenguaje RAII de C ++ y presente en Rust también hace cosas que superficialmente parecen llamadas de cola, no llamadas de cola (porque los "destructores" todavía necesitan ser llamados). Ha habido propuestas para usar una sintaxis diferente para optar por una semántica ligeramente diferente que permitiría la recursión de cola (es decir, los destructores de llamadas antesla última llamada final y, obviamente, no permitir el acceso a objetos "destruidos"). (La recolección de basura no tiene ese problema, y ​​todos Haskell, SML y Scheme son idiomas recolectados de basura.) En una vena muy diferente, algunos idiomas, como Smalltalk, exponen la "pila" como un objeto de primera clase. en los casos, la "pila" ya no es un detalle de implementación, aunque esto no impide tener tipos separados de llamadas con semántica diferente. (Java dice que no puede debido a la forma en que maneja algunos aspectos de la seguridad, pero en realidad esto es falso ).

En la práctica, la prevalencia de implementaciones interrumpidas de llamadas a funciones proviene de tres factores principales. Primero, muchos lenguajes heredan la implementación rota de su lenguaje de implementación (generalmente C). En segundo lugar, la gestión determinista de los recursos es agradable y hace que el problema sea más complicado, aunque solo un puñado de idiomas lo ofrecen. En tercer lugar, y, en mi experiencia, la razón por la que la mayoría de las personas se preocupan es porque quieren rastrear el stack cuando ocurren errores con fines de depuración. Solo la segunda razón es una que puede estar potencialmente motivada teóricamente.

Básicamente, la diferencia es que la recursividad incluye una pila, una estructura de datos auxiliar que probablemente no desee, mientras que los bucles no lo hacen automáticamente. Solo en casos excepcionales, un compilador típico puede deducir que, en realidad, no necesita la pila.

Si compara en cambio bucles que operan manualmente en una pila asignada (por ejemplo, a través de un puntero a la memoria de almacenamiento dinámico), normalmente no los encontrará más rápido o incluso más lento que usar la pila de hardware.