Home Original page

Recursively traverse linked list -- help!

Terry Reedy tjreedy at home.com
Wed Feb 20 11:13:33 EST 2002 
Someone who does not understand Python sematics claimed (incorrectly):

> > > > That's ok in Scheme but I don't think any current Python
implementations
> > > > handle tail recursion "correctly".

and clarified

> > 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.

Steve Holden responded

> 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).

Correct.  As Guido explained when this same issue came up some months
ago ...

Automatic (hidden) tail recursion removal would be semanticly
*incorrect* for Python because it assumes (incorrectly, in general)
that the association between a particular name and a particular
function object is permanent.  In other words, the compiler cannot
tell whether a return statement that looks like tail recursion really
is tail recursion or will remain tail recursion even when it initially
is.  Python is not Scheme.

Consider the following legal and possibly even sensible (when fleshed
out) code:

def f1(val): return 1

def f2(val): return 2

def f(val):
  global f
  f = val and f1 or f2
  return f(val)

>>> f
<function f at 785ee0>
>>> f(0)
2
>>> f
<function f2 at 786be0>

When the assumption of fixed association *is* correct, the programmer
can easily do the standard translation to loop form if desired.

Terry J. Reedy
More information about the Python-list mailing list