Austin Ziegler wrote:
>>import sys
>>sys.setrecursionlimit(5000000)
> 
> This is a bit of a cheat, IMO, to do this within Python. I suspect
> that it could be done within Ruby, ...

So what?  The alioth benchmark can be faulted because it does not 
recognize the need for an external "ulimit" in some cases, but the 
overhead for recursion is quite obvious and painful in Ruby, and the 
limit on stack depth is *much* worse on most WinXP machines, and those 
machines don't have ulimit.

> IN REALITY, we see that Python -- without this
> setting change -- can't even finish Ack(3,7).

I really don't see the point here.  We're should be focusing on two 
things: the time overhead for each level of recursion, and the overall 
limit on stack depth.  Now, if you don't give your interpreter enough 
room, the stack will overflow, and what exactly have you proven?  If you 
drive most cars off the road and into a ditch they will usually stop 
moving, too, but that only proves that the driver is bad, not the car.

The actual method by which stack allocation is increased is not very 
interesting, as long as there is *some* way to do it.  After you have 
arranged for a large enough stack, the only thing left is time overhead 
per level of recursion.

This is bad enough in Ruby that I start thinking of ways to avoid deep 
recursion in my algorithms long before I'm at the strategically 
appropriate time to be doing optimization, because it is just about 
always guaranteed to be a problem.

Tail recursion would be nice, but not sufficient.  Ruby needs to be 
"stackless", in the sense that the Ruby stack should not be entangled 
with the stack of the executable.  This would make it much easier to 
recurse as deep as available memory will allow.

-- 
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoil.com/>