Recursively traverse linked list -- help!

[Paul Rubin]

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.