Help- Recursion v. Iter Speed comparison
roy at panix.com
Wed Mar 2 14:41:05 CET 2005
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
More information about the Python-list