[Python-Dev] Proper tail recursion

Michael Chermside mcherm at mcherm.com
Thu Jul 15 14:32:05 CEST 2004


Drat!

I mis-clicked the "Send" button before finishing my previous email.

Here's the entire thing:

Christopher King writes:
> To tell the truth, I don't really have any immediate use for this
> functionality, either, but since it turned out to be so
> easy to implement,
> I ask, "why not?" ;)

Martin replies:
> The traditional answer to that question is "because Jython cannot
> support it".

No... that answer applies to *language features*, but not *implementation
details*. The recursion limit (the value of it anyhow) is an
implementation detail.

Think of it this way: if Iron Python, Jython, or PyPy were to implement
a clever trick that made loops run 10x faster, that would be swell,
even if the same trick couldn't be done in CPython. If CPython can find
a way to run recursion far more efficiently, then that's swell too. Of
course, the actual results from running the program must not differ,
but that doesn't seem too difficult to achieve.

Guido writes:
> I'm not interested in adding this to the official Python release.
>
> One reason is that if an exception happens in such a tail-recursive
> call, the stack trace will be confusing.

This doesn't bother me as much as it apparently bothers you. But for
that matter, we hardly care about performance if we're going to be
generating a stack trace, so we could probably construct the stack
trace after-the-fact if needed.

Guido continues:
> Another reason is that I don't think it's a good idea to try to
> encourage a Scheme-ish "solve everything with recursion" programming
> style in Python.

I wouldn't say that tail recursion *encouraged* a functional style,
rather I would say that refusing to accept a working version of
tail recursion actively *discourages* the use of that style.

Now, I understand that a functional style is not for everybody. And
I realize that you want to design Python so that people will continue
to use it to write programs that are readable (and understandable)
by everyone. But I believe strongly in allowing different programming
paradigms -- using procedural, OOP, or functional programming styles
(and others) for the particular problems that they express best.
And I think that *discouraging* a functional style by intentionally
breaking it is a bad idea.

Rejecting an implementation of tail recursion because it doesn't
work well or it slows down other cases is perfectly reasonable. But
rejecting it because it allows some people's programs to work better...
that just seems wrongheaded.

-- Michael Chermside





More information about the Python-Dev mailing list