Iteration over recursion?

[Nick Maclaren]

In article <1150816827.826028.114740 at h76g2000cwa.googlegroups.com>,
"Jon Clements" <joncle at googlemail.com> writes:
|> MTD wrote:
|> 
|> > I've been told that iteration in python is generally more
|> > time-efficient than recursion. Is that true?
|> 
|> 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.

Well, vaguely.  That is probably the case in Python, but it isn't always
true, and is not the only issue.

Tail recursion removal can often eliminate the memory drain, but the
code has to be written so that will work - and I don't know offhand
whether Python does it.

In compiled "3rd GL" languages, there are a lot of optimisation issues
where iteration will often produce better code than recursion, but few
(if any) are relevant to Python.


Regards,
Nick Maclaren.