Efficiency: recursion vs loop

Question

This is just curiosity on my part, but what is more efficient, recursion or a loop?

Given two functions (using common lisp):

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

and

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

Which is more efficient?

Answer 1

I don't even have to read your code.

Loop is more efficient for factorials. When you do recursion, you have up to x function calls on the stack.

You almost never use recursion for performance reasons. You use recursion to make the problem more simple.

Answer 2

Mu.

Seriously now, it doesn't matter. Not for examples this size. They both have the same complexity. If your code is not fast enough for you, this is probably one of the last places you'd look at.

Now, if you really want to know which is faster, measure them. On SBCL, you can call each function in a loop and measure the time. Since you have two simple functions, time is enough. If your program was more complicated, a profiler would be more useful. Hint: if you don't need a profiler for your measurements, you probably don't need to worry about performance.

On my machine (SBCL 64 bit), I ran your functions and got this:

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 

After putting your functions in a file with (declaim (optimize speed)) at the top, the recursion time dropped to 504 milliseconds and the loop time dropped to 475 milliseconds.

And if you really want to know what's going on, try dissasemble on your functions and see what's in there.

Again, this looks like a non-issue to me. Personally, I try to use Common Lisp like a scripting language for prototyping, then profile and optimize the parts that are slow. Getting from 500ms to 475ms is nothing. For instance, in some personal code, I got a couple of orders of magnitude speedup by simply adding an element type to an array (thus making the array storage 64 times smaller in my case). Sure, in theory it would have been faster to reuse that array (after making it smaller) and not allocate it over and over. But simply adding :element-type bit to it was enough for my situation - more changes would have required more time for very little extra benefit. Maybe I'm sloppy, but 'fast' and 'slow' don't mean much to me. I prefer 'fast enough' and 'too slow'. Both your functions are 'fast enough' in most cases (or both are 'too slow' in some cases) so there's no real difference between them.