11

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.

10

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

1

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

  • 1
    Did you look at the programs? The iterative factorial doesn't manipulate a stack at all. – AProgrammer Jun 25 '11 at 19:20
-1

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.

  • Those were from the SBCL code, I think. – martinjacobd Jun 25 '11 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.