¿Por qué la versión iterativa tarda más?

Respuestas:

10

Los dos programas no son equivalentes. La versión recursiva es informática

(... ((1 * 2) * 3) * 4 ... * n)

mientras que el iterativo es la computación

(... ((n * (n-1)) * (n-2) ... * 1)

por lo tanto, las cantidades intermedias están creciendo más rápidamente para la versión iterativa y el cálculo de números grandes es más rápido cuando los números involucrados son pequeños (¡Computar 1000! sin números grandes no tiene sentido y el dialecto lisp cambia automáticamente a números grandes).

Un programador
fuente
1

Cuando hace que un algoritmo recursivo sea iterativo, debe implementar explícitamente la pila que rastrea los resultados. Este acto agrega operaciones adicionales que tratan de empujar y reventar la pila que el algoritmo recursivo obtiene de forma gratuita (bueno, no del todo gratis, pero las operaciones adicionales suman más que el costo de la recursividad).

Michael Brown
fuente
1
¿Viste los programas? El factorial iterativo no manipula una pila en absoluto.
Programador
-1

Solo puedo adivinar, ni siquiera estoy seguro de si esos puntos de referencia son del código C o del código SBLC. Mi suposición es que el culpable está mutando la variable. 1000! es un número bastante grande, tal vez es más rápido llenar la pila con intermediarios y limpiar que crear una copia y sobrescribirla.

Gabriel Ščerbák
fuente
Esos eran del código SBCL, creo.
martinjacobd