Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers

up vote 9 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
add comment

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
1  
Sorry...I was generalizing I didn't se the original code because he didn't have it linked when he posted the original q. Try not to be a Richard Nixon. –  Mike Brown Jun 26 '11 at 3:00
add comment

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
add comment

Your Answer

 
discard

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.