Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was looking over at 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.

share|improve this question
up vote 10 down vote accepted

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

share|improve this answer

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

share|improve this answer
Did you look at the programs? The iterative factorial doesn't manipulate a stack at all. – AProgrammer Jun 25 '11 at 19:20

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.

share|improve this answer
Those were from the SBCL code, I think. – martinjacobd Jun 25 '11 at 17:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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