Iteration over recursion?

[Jon Clements]

MTD wrote:
> Hello all,
>

(snip)

> I've been told that iteration in python is generally more
> time-efficient than recursion. Is that true?

(snip)

AFAIK, in most languages it's a memory thing. Each time a function
calls itself, the 'state' of that function has to be stored somewhere
so that it may continue, as was, when the recursive function returns.
Therefore, you can effectively think of it as creating N many objects
which don't start getting released until the very last nested call
returns. This (depending on the stack size and implementation etc...)
may force several memory allocations. Then of course, as it starts
going back 'upwards' (towards the initiator of the recursive call that
is), the garbage collector may kick in freeing memory...

Depending on return values, iterating will just require space for the
returned value from each function in term (which in most cases - I
would imagine fits on the stack), so although it's doing effectively
the same thing, it's doing so with less memory.

I probably haven't explained too well, and I may not even be right. So
take with a pinch of salt.

All the best,

Jon.