Recursively traverse linked list -- help!

[Steve Holden]

"Paul Rubin" <phr-n2002a at nightsong.com> wrote in message
news:7xeljg7h7b.fsf at ruckus.brouhaha.com...
> yhatakka at dlc.nospam.fi (Yrjö Hatakka) writes:
> > >> def traverse(list):
> > >>     if list:
> > >>         print list[0]  # or do something here
> > >>         traverse(list[1:])
> > >>     else:
> > >>         print "done"
> > >>
> > >
> > > That's ok in Scheme but I don't think any current Python
implementations
> > > handle tail recursion "correctly".
> >
> > What do you mean? I tried above an it seems to work. When does it stop
> > working?
>
> By "correctly" I mean the code should be executed without pushing
> another recursive call onto the call stack for every list element.
> The recursive call should instead be compiled as a jump back to the
> top of the function.  I don't remember seeing it documented anywhere
> that Python does that.  Even if the current implementation happens to
> transform tail recursion like that, it's an implementation-specific
> optimization rather than part of the language definition like it is in
> Scheme.

Please remove your Scheme prejudices before treading in the Python world -
quotation marks notwithstanding. The remark you originally made was like an
obscure line of code that needed ten lines of comment to justify it :-)

All the tail recursion optimization does is speed things up slightly and
avoid stack exhaustion at high recursion depths. No wonder you felt the need
to quote "correctly".

For what it's worth, no current implementations of Python implement such
tail recursion optimization (AFAIK).

lots-of-better-ways-to-optimize-before-that-ly y'rs  - steve
--
Consulting, training, speaking: http://www.holdenweb.com/
Author, Python Web Programming: http://pydish.holdenweb.com/pwp/

"This is Python.  We don't care much about theory, except where it
intersects with useful practice."  Aahz Maruch on c.l.py