[Python-Dev] Proper tail recursion (original) (raw)

Andrew Koenig ark-mlist at att.net
Thu Jul 15 16:53:37 CEST 2004

> How about: Tail recursion "enables" recursion-oriented (functional) > style? :)

Still -1. I was understating my case: I find the "recursion is the basis of everything" attitude harmful.

I don't believe that recursion is the basis of everything. Nevertheless, I do think that there are some algorithms that are much more easily expressed in recursive than in iterative terms, and I wish that Python did not impose a fixed limit on recursion depth. For example:

def traverse(t, f):
    if t:
        f(t)
        traverse(t.left)
        traverse(t.right)

This code has the unfortunate limitation of being unable to traverse a tree deeper than the recursion limit. I can use tail-recursion elimination to remove this restriction for one branch of each node:

def traverse(t, f):
    while t:
        f(t)
        traverse(t.left)
        t = t.right

which makes the code much more useful if the "trees" are really lists according to Lisp conventions (i.e. the left branch of each node is usually short), but I would really rather that the compiler did this transformation for me, as I find the first version much easier to understand than the second.

If I really want to work around the recursion limit altogether, I have to define a stack of my own:

def traverse(t, f):
    s = [t]
    while s:
        t = s.pop()
        if t:
            f(t)
            s.append(t.right)
            s.append(t.left)

Now I am free of the recursion-depth limitation, but the code has become complicated enough to reduce my confidence in its correctness.

So I agree that recursion is not the basis of everything--but it is the basis of some things, and I would like to be able to express those things recursively without having to worry about the implementation stopping me. I understand that the existence of Jython may make this wish impossible to achieve in practice, but it's still there.

More information about the Python-Dev mailing list