[Python-Dev] Proper tail recursion

[Andrew Koenig]

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