[Python-ideas] A Continuations Compromise in Python

[Steven D'Aprano]

On Mon, 4 May 2009 01:16:10 am Antoine Pitrou wrote:

> > In this case, two recursive calls (one of which is a tail-call)
> > takes nearly 60% more time than a single recursive call in a while
> > loop.
>
> Why do you think recursion has anything to do with it, rather than
> simply the fact that there are twice more function calls?

But surely that's the point of removing tail-recursion? Each function 
call has overhead, and by reducing the number of function calls, you 
reduce the amount of overhead.

Perhaps we're not discussing the same thing? After reading your reply, 
there does seem to be some confusion (at least in my head) as to what 
precisely we're talking about. I've seen tail-call optimization 
described as programatically converting a tail-call recursive function 
into an equivalent iterative function. I've also seen it referring to a 
process of minimizing the depth of the function call stack while still 
making the same number of function calls.


> Besides, I object to the claim that solving the Towers of Hanoï
> problem is a real-world example ;)

Well, I did admit it was a toy :)


> That said, it's true that recursive calls are probably costlier than
> non-recursive ones, due to the fact that only one frame object is
> cached for each code objects. But removing this limitation shouldn't
> make the common (non-recursive) case slower, and it shouldn't
> increase memory consumption too much, so it's not as easy as it
> seems.

I don't think anyone really believes it is easy. Even the people on 
various blog sites saying it's "easy" are actually saying that a 
solution which is either fragile, or slow, or both, is easy, and that 
shouldn't surprise anyone.



-- 
Steven D'Aprano