Eficiencia: recursion vs loop

Question

Esto es solo curiosidad por mi parte, pero ¿qué es más eficiente, recursión o un ciclo?

Dadas dos funciones (utilizando Common Lisp):

(defun factorial_recursion (x) 
    (if (> x 0) 
     (* x (factorial_recursion (decf x))) 
     1)) 

y

(defun factorial_loop (x) 
    (loop for i from 1 to x for result = 1 then 
     (* result i) finally 
     (return result))) 

que es más eficiente?

Answer 1

Ni siquiera tengo que leer su código.

Loop es más eficiente para los factoriales. Cuando realiza recursividad, tiene hasta x llamadas de función en la pila.

Casi nunca usa recursividad por motivos de rendimiento. Usas recursion para hacer el problema más simple.

Answer 2

Si usted puede escribir funciones recursivas de tal manera que la llamada recursiva es la última cosa hecho (y la función es, pues, recursiva de cola) y el lenguaje y el compilador/intérprete que está utilizando admite recursividad de cola, luego la función recursiva puede (normalmente) optimizarse en un código que es realmente iterativo, y es tan rápido como una versión iterativa de la misma función.

Sam I Am es correcto, sin embargo, las funciones iterativas son generalmente más rápidas que sus contrapartes recursivas. Si una función recursiva debe 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 a la función es mucho más costosa que un salto, además de que consume espacio en la pila, un recurso (muy) finito.

La función que le da no es recursiva de cola porque llama al factorial_recursion y luego la multiplica 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)) 

Answer 3

Aquí está un factorial recursiva de cola (creo):

(defun fact (x) 
    (funcall (alambda (i ret) 
      (cond ((> i 1) 
        (self (1- i) (* ret i))) 
        (t 
        ret))) 
      x 1)) 

Answer 4

Mu.

En serio ahora, no importa. No por 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, medirlos. En SBCL, puede llamar a cada función en un bucle y medir la hora. Como tiene dos funciones simples, es suficiente con time. Si su programa era más complicado, un profiler sería más útil. Sugerencia: si no necesita un generador de perfiles para sus mediciones, probablemente no tenga que preocuparse por el rendimiento.

En mi máquina (SBCL 64 bits), me encontré con sus funciones y se puso 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 recurrencia se redujo a 504 milisegundos y la el tiempo de bucle cayó a 475 milisegundos.

Y si realmente quieres saber qué está pasando, prueba dissasemble en tus funciones y mira lo que hay allí.

De nuevo, esto no parece un problema para mí. Personalmente, trato de usar Common Lisp como un lenguaje de scripting para prototipos, luego perfilo y optimizo las partes que son lentas. Pasar de 500 ms a 475 ms no es nada. Por ejemplo, en algún código personal, obtuve un par de órdenes de aceleración de mayor magnitud simplemente agregando un tipo de elemento a una matriz (lo que hace que el almacenamiento de la matriz sea 64 veces más pequeño en mi caso). Claro, en teoría hubiera sido más rápido reutilizar esa matriz (después de hacerla más pequeña) y no asignarla una y otra vez. Pero simplemente agregar :element-type bit fue suficiente para mi situación: más cambios habrían requerido más tiempo con muy poco beneficio adicional. 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 existe una diferencia real entre ellas.