Help- Recursion v. Iter Speed comparison

[Roy Smith]

actuary77 <actuary77 at elemental-systems.com> wrote:

> Recurse from 9999 time: 4.3059999942779541 seconds
> 
> Iter from 9999 time: 0.0099999904632568359 seconds
> 
> No comparison, why is recursion so slow?

I believe Edouard Manet said it best, "Damn your recursion, Henri. 
Iteration, however complex, is always more efficient." (extra points if you 
can identify the source of that quote).  It's not clear what language Manet 
was talking about when he said that, but it's pretty much a universal truth.

There's a fair amount of overhead in a function call.  You've got to push 
the arguments (and whatever state you need to save) onto the stack, and 
when the function returns, all that has to be undone.  Depending on the 
language, this may involve building temporary copies of objects.  If the 
function is small, the call-return overhead may totally swamp the real work 
done.