# [Python-Dev] Proper tail recursion

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.

```