[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