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?

Bilharziasis

If your function is tail-recursive, it is fundamentally identical to a loop. The tail recursion can get optimized into a simple loop, making them identical. Your function is not tail-recursive, though. – Chronological

@Gabe, While tail recursion may be optimised to a loop it is worth noting that Common Lisp implementations are not required to optimise tail calls, although many implementations do. – Knp

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.

Galbraith

This is true for most cases but recursion introduces easier reasoning and if your compiler supports tail-call optimization then it may possibly still be as fast as an iterative function since the recursive function would then be transformed into a loop on compile. So you have the speed of an iterative function with the ease of reasoning by a recursive function. – Blessed

@AdrianLegaspi even so, doesn't that mean iteration is more efficient? – Shaunna

@Shaunna It is a case-to-case basis on which is more efficient, some operations are faster in stack, some operations are faster on iteration. A single point of comparison has a bias towards the use-case of recursion and iteration, in this case; Iteration is much faster. In that sense, it's a matter of how a language processes the code also, as I've mentioned, some compilers transformers a recursion into a loop on its binary depending on its computation on that code. e.g. GHC – Blessed

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.

Atony

Answer 3

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))

Querist

The Common Lisp standard does not mention tail recursion in any way. Some CL compilers support it though. One needs to read their manual to see how to force the compiler to do TCO. – Tillfourd

@RainerJoswig yeah, that's why I mentioned the compiler/interpreter too in the list of prerequisites for tail recursion – Querist

... Tail recursion optimisation, that is – Querist

Answer 4

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))

Marceline

Answer 5

Rule of Thumb-

1. Loops are always more performance efficient than recursion given any language.
2. Recursion always reduce the boilerplate code written for Loops.

For more internal details, please read.

Weidman