[Python-Dev] Tail recursion

François Pinard pinard at iro.umontreal.ca
Fri Nov 28 11:44:12 EST 2003

[Tim Peters]
> [Andrew Koenig]
> > Ah.  I will agree with you that wholly tail-recursive programs are
> > usually no easier to understand than their iterative counterparts.

> Good!  That's why I've never been keen to "do something" about tail
> recursion in Python -- the "one obvious way" to write a loop in Python is
> with a loop <wink>.

Just a tiny remark on that topic.  In my experience, it is rather
unusual that I need to use tail recursion in a way that would not easily
express itself with a simple loop, and more clearly that way.

However, there are a few rare cases in which algorithms use tail
recursion at various places and paths in a single function, in such a
way that untangling these into a single loop would not be easy.  But
such situtations (let's call them [1]) are uncommon in practice.

Moreover, tail recursion is an optimisation matter, and situations in
which speed is excruciatingly important (let's call them [2]) are far
less frequent, still in practice, than some people tend to believe.

Since [1] and [2] are kind of independant, we could consider that it
is extremely uncommon that we meet [1] and [2] simultaneously.  So, in
practice, it might be that Python does not really need tail recursion.

> > On the other hand, there are partially tail-recursive functions that
> > I find easier to understand, such as [...]

Yes, of course, if an algorithm expresses itself more clearly using
a notation which happens to be tail recursive, do not hesitate at
expressing it that way, especially given that _on average_, one may
safely assert that the algorithm is not speed-critical.  Rare exceptions
exist and can be used to build counter-examples, but these should not be
seen as really compelling.

On the other hand, if Guido feels like accepting tail-recursion in
Python for the sake of an intellectual exercise or for the pleasure of
its elegance, let's go for it.  It cannot really hurt that much :-).

François Pinard   http://www.iro.umontreal.ca/~pinard

More information about the Python-Dev mailing list