Why does the iterative version take longer?

Question

I was looking over at http://programming.lispdream.com/blog/2011/06/recursion-vs-iteration/ and I saw that on his implementation of the recursive and iterative implementations of the factorial function, the iterative actually takes longer given n = 1,000. I can't figure out why (he doesn't explain, but says that it is an exercise for the reader). Sorry for my newness to all of this.

Answer 1

The two programs aren't equivalent. The recursive version is computing

(...((1*2)*3)*4 ... *n)

while the iterative one is computing

(...((n*(n-1))*(n-2) ... * 1)

thus intermediate quantities are growing more rapidly for the iterative version and big num computation is quicker when the numbers involved are small (Computing 1000! without big num has no sense and lisp dialect switch to big num automatically).

Answer 2

When you make a recursive algorithm iterative, you have to explicitly implement the stack that tracks results. This act adds extra operations dealing with pushing and popping the stack that the recursive algorithm gets for free (well not quite for free but the extra operations add up to more than the cost of recursion).

Answer 3

I can only guess, I am not even sure if those benchmarks are from the C or from the SBLC code. My guess is the culprit is mutating the variable. 1000! is a pretty big number, maybe it is faster to populate stack with intermidiaries and clean up than to create a copy and overwrite.