Buscamos por todo el mundo online para así darte la solución a tu duda, si tienes alguna inquietud puedes dejar tu duda y te contestamos sin falta.
Solución:
Ni siquiera tengo que leer tu código.
Loop es más eficiente para factoriales. Cuando haces recursividad, tienes hasta X llamadas de función en la pila.
Casi nunca usa la recursividad por razones de rendimiento. Utiliza la recursividad para simplificar el problema.
Mu.
Ahora en serio, no importa. No para ejemplos de este tamaño. Ambos tienen la misma complejidad. Si su código no es lo suficientemente rápido para usted, este es probablemente uno de los últimos lugares que miraría.
Ahora, si realmente quieres saber cuál es más rápido, mídelos. En SBCL, puede llamar a cada función en un bucle y medir el tiempo. Como tienes dos funciones simples, time es suficiente. Si su programa fuera más complicado, un generador de perfiles sería más útil. Sugerencia: si no necesita un generador de perfiles para sus mediciones, probablemente no necesite preocuparse por el rendimiento.
En mi máquina (SBCL de 64 bits), ejecuté sus funciones y obtuve esto:
CL-USER> (time (loop repeat 1000 do (factorial_recursion 1000)))
Evaluation took:
0.540 seconds of real time
0.536034 seconds of total run time (0.496031 user, 0.040003 system)
[ Run times consist of 0.096 seconds GC time, and 0.441 seconds non-GC time. ]
99.26% CPU
1,006,632,438 processor cycles
511,315,904 bytes consed
NIL
CL-USER> (time (loop repeat 1000 do (factorial_loop 1000)))
Evaluation took:
0.485 seconds of real time
0.488030 seconds of total run time (0.488030 user, 0.000000 system)
[ Run times consist of 0.072 seconds GC time, and 0.417 seconds non-GC time. ]
100.62% CPU
902,043,247 processor cycles
511,322,400 bytes consed
NIL
Después de poner sus funciones en un archivo con (declaim (optimize speed)) en la parte superior, el tiempo de recursión se redujo a 504 milisegundos y el tiempo de bucle se redujo a 475 milisegundos.
Y si realmente quieres saber qué está pasando, prueba dissasemble en sus funciones y ver lo que hay allí.
Una vez más, esto no me parece un problema. Personalmente, trato de usar Common Lisp como un lenguaje de secuencias de comandos para la creación de prototipos, luego perfilo y optimizo las partes que son lentas. Pasar de 500ms a 475ms no es nada. Por ejemplo, en algún código personal, obtuve un par de órdenes de aceleración de magnitud simplemente agregando un tipo de elemento a un array (haciendo así el array almacenamiento 64 veces menor en mi caso). Claro, en teoría habría sido más rápido reutilizar eso array (después de hacerlo más pequeño) y no asignarlo una y otra vez. Pero simplemente agregando :element-type bit fue suficiente para mi situación: más cambios habrían requerido más tiempo para un beneficio adicional muy pequeño. Tal vez soy descuidado, pero ‘rápido’ y ‘lento’ no significan mucho para mí. Prefiero ‘lo suficientemente rápido’ y ‘demasiado lento’. Ambas funciones son ‘lo suficientemente rápidas’ en la mayoría de los casos (o ambas son ‘demasiado lentas’ en algunos casos), por lo que no hay una diferencia real entre ellas.
Si puede escribir funciones recursivas de tal manera que la llamada recursiva sea lo último hecho (y la función es por lo tanto cola recursiva) y el lenguaje y el compilador/intérprete que está utilizando admite la recursión de cola, luego la función recursiva puede (generalmente) optimizarse en un código que es realmente iterativo y es tan rápido como una versión iterativa de la misma función.
Sin embargo, Sam I Am tiene razón, las funciones iterativas suelen ser más rápidas que sus contrapartes recursivas. Si una función recursiva va a ser tan rápida como una función iterativa que hace lo mismo, debe confiar en el optimizador.
La razón de esto es que una llamada de función es mucho más caro que un salto, además de consumir espacio de pila, un recurso (muy) finito.
La función que das no es recursiva de cola porque llamas factorial_recursion y luego lo multiplicas por x. Un ejemplo de una versión recursiva de cola sería
(defun factorial-recursion-assist (x cur)
(if (> x 1)
(factorial-recursion-assist (- x 1) (+ cur (* (- x 1) x)))
cur))
(defun factorial-recursion (x)
(factorial-recursion-assist x 1))
(print (factorial-recursion 4))
Si te gusta este mundo, eres capaz de dejar un artículo acerca de qué te ha gustado de este tutorial.