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

If you can write recursive functions in such a way that the recursive call is the very last thing done (and the function is thus tail-recursive) and the language and compiler/interpreter you are using supports tail recursion, then the recursive function can (usually) be optimised into code that is really iterative, and is as fast as an iterative version of the same function.

Sam I Am is correct though, iterative functions are usually faster than their recursive counterparts. If a recursive function is to be as fast as an iterative function that does the same thing, you have to rely on the optimiser.

The reason for this is that a function call is much more expensive than a jump, plus you consume stack space, a (very) finite resource.

The function you give is not tail recursive because you call factorial_recursion and then you multiply it by x. An example of a tail-recursive version would be

(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 2

Here's a tail-recursive factorial (I think):

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

Answer 3

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 4

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.