# Ruby and recursion (Ackermann benchmark)

**URL:** <https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969>\
**Category:** ruby-talk\
**Created:** [14 June 2005 17:40 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969 "2005-06-14T17:40:31Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ptkwt](https://avatars.discourse-cdn.com/v4/letter/p/f14d63/32.png) [@Ptkwt](https://rubytalk.org/u/Ptkwt)\
**Post date:** [14 June 2005 17:40 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/1 "2005-06-14T17:40:31Z")

</div>

Amidst all of the discussion about the alioth benchmarks and how they are  
(insert disparaging term here) there was a little discussion about the  
Ackermann benchmark and how Ruby finishes dead last even behind gawk(in  
fact doesn't finish for values of N larger than 6).

Here's the benchmark code:

&nbsp;&nbsp;def ack(m, n)  
&nbsp;&nbsp;&nbsp;&nbsp;if m == 0 then  
&nbsp;&nbsp;n + 1  
&nbsp;&nbsp;&nbsp;&nbsp;elsif n == 0 then  
&nbsp;&nbsp;ack(m - 1, 1)  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;ack(m - 1, ack(m, n - 1))  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end

&nbsp;&nbsp;NUM = Integer(ARGV.shift || 1)  
&nbsp;&nbsp;print "Ack(3,", NUM, "): ", ack(3, NUM), "\n"

Well, that's simple enough. Nothing to improve there and essentially  
looks like the Python version, except that the python version includes:

&nbsp;&nbsp;import sys  
&nbsp;&nbsp;sys.setrecursionlimit(5000000)

....kind of handy that they can do that from within their program.

So the conclusion is that Ruby isn't so great at recursion (not a new  
conclusion). If you're looking for a language that's good for recursion  
(because you like that style of programming or whatever) then looking at  
the results of this benchmark would be informative. You could tell right  
away that Ruby isn't a good choice for that style of programming. One  
might dismiss this by saying "well, I never use recursion anyway", but a  
lot of algorithms are much easier to implement recusively (algorithms  
which deal with walking trees for example).

That brings up the question: why is Ruby so bad at recursion?  
Is it possible to improve (and at what are the tradeoffs)?

Phil

---

<div class="post-metadata">

**Author:** ![Austin\_Ziegler5](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/austin_ziegler5/32/1985_2.png) [@Austin\_Ziegler5](https://rubytalk.org/u/Austin_Ziegler5)\
**Post date:** [14 June 2005 18:59 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/2 "2005-06-14T18:59:03Z")

</div>

> Amidst all of the discussion about the alioth benchmarks and how  
> they are (insert disparaging term here) there was a little  
> discussion about the Ackermann benchmark and how Ruby finishes  
> dead last even behind gawk(in fact doesn't finish for values of N  
> larger than 6).

[snipped benchmark]

> Well, that's simple enough. Nothing to improve there and  
> essentially looks like the Python version, except that the python  
> version includes:
> 
> import sys  
> sys.setrecursionlimit(5000000)
> 
> ....kind of handy that they can do that from within their program.

This is a bit of a cheat, IMO, to do this within Python. I suspect  
that it could be done within Ruby, but I think that Matz had  
indicated that this is more appropriately an operating system  
function. Indeed:

&nbsp;&nbsp;austin@austin:~$ time ack.rb 7  
&nbsp;&nbsp;Ack(3,7): 1021

&nbsp;&nbsp;real 0m1.258s  
&nbsp;&nbsp;user 0m1.230s  
&nbsp;&nbsp;sys 0m0.010s

&nbsp;&nbsp;austin@austin:~$ ulimit -s 16384  
&nbsp;&nbsp;austin@austin:~$ time ack.rb 8  
&nbsp;&nbsp;Ack(3,8): 2045

&nbsp;&nbsp;real 0m5.306s  
&nbsp;&nbsp;user 0m5.250s  
&nbsp;&nbsp;sys 0m0.030s

&nbsp;&nbsp;austin@austin:~$ time ack.rb 9  
&nbsp;&nbsp;Ack(3,9): 4093

&nbsp;&nbsp;real 0m22.707s  
&nbsp;&nbsp;user 0m22.520s  
&nbsp;&nbsp;sys 0m0.150s  
&nbsp;&nbsp;austin@austin:~$ ruby -v  
&nbsp;&nbsp;ruby 1.8.2 (2005-03-10) [i686-linux]

Thus, by changing ulimit in the user level, I can do the Ackermann  
test. That is a linode, by the way, with 96 Mb of memory. Comparing  
like to like, I get:

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;7 8 9  
Python 0.643 3.071 11.519  
Python-s DNF DNF DNF  
Python-u DNF DNF DNF  
Ruby 1.234 DNF DNF (1933 levels)  
Ruby-u 1.210 5.319 23.275  
Perl 0.835 3.659 20.935

Python-s removes the setrecursion limit; Python-u does the same but  
changes ulimit. IN REALITY, we see that Python -- without this  
setting change -- can't even finish Ack(3,7). (The variance in the  
test table above and my earlier results is that they were run at  
different times.)

Ruby, on the other hand, does finish it with this OS setting. I  
suspect that the stack frames (bindings) in Ruby are larger, which  
explains the speed difference to some degree. Could Ruby be faster?  
We're pretty competitive with Perl there. Probably. I wouldn't know  
the first thing about speeding it up -- or if we really need to.

> So the conclusion is that Ruby isn't so great at recursion (not a  
> new conclusion). If you're looking for a language that's good for  
> recursion (because you like that style of programming or whatever)  
> then looking at the results of this benchmark would be  
> informative. You could tell right away that Ruby isn't a good  
> choice for that style of programming. One might dismiss this by  
> saying "well, I never use recursion anyway", but a lot of  
> algorithms are much easier to implement recusively (algorithms  
> which deal with walking trees for example).

But it would be an incorrect assumption -- remember, I changed a  
userspace OS-level value from 8192 (the default stack size in  
kilobytes) to 16384, and was able to do ack(3,9). It blew up on  
ack(3, 10) -- but I can't change the stack any larger. However, we  
went from blowing up around 1500 levels to 4500 levels of recursion.

This is \*part\* of the reason that I have significant issues with the  
alioth shootout. They don't take any responsibility for these  
numbers or understanding the nature of problems -- and seem to be  
proud of it. They've accepted a Perl version that goes for fast-and-  
ugly:

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# in our quest for speed, we must get ugly:  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# it helps reduce stack frame size a little bit  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# from Leif Stensson  
&nbsp;&nbsp;&nbsp;&nbsp;sub Ack {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return $\_[0] ? ($\_[1] ? Ack($\_[0]-1, Ack($\_[0], $\_[1]-1))  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;: Ack($\_[0]-1, 1))  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;: $\_[1]+1;  
&nbsp;&nbsp;&nbsp;&nbsp;}

All because it's "prettier but slower to do this":

&nbsp;&nbsp;&nbsp;&nbsp;sub Ack {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;my($M, $N) = @\_;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return( $N + 1 ) if ($M == 0);  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return( Ack($M - 1, 1) ) if ($N == 0);  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Ack($M - 1, Ack($M, $N - 1));  
&nbsp;&nbsp;&nbsp;&nbsp;}

IMO, this is completely inappropriate. If the Perlers are going to  
do things to reduce their stack frames, and the Pythonistas are  
going to muck around with recursion limits that help their code run  
at all ... why can't Rubyists reduce or eliminate the recursion  
entirely?

-austin

> **···**
>
> On 6/14/05, Phil Tomson \<ptkwt@aracnet.com\> wrote:  
> --  
> Austin Ziegler \* halostatue@gmail.com  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\* Alternate: austin@halostatue.ca

---

<div class="post-metadata">

**Author:** ![Logan\_Capaldo](https://avatars.discourse-cdn.com/v4/letter/l/7ea924/32.png) [@Logan\_Capaldo](https://rubytalk.org/u/Logan_Capaldo)\
**Post date:** [14 June 2005 19:12 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/3 "2005-06-14T19:12:27Z")

</div>

Ok I realize that this (definitely) probably won't make it any faster  
but could some clever hacker use callcc to implement a CPS version? It  
would still technically be recursive, but should bypass the stack  
(almost) entirely.

> **···**
>
> On 6/14/05, Austin Ziegler \<halostatue@gmail.com\> wrote:
> 
> > On 6/14/05, Phil Tomson \<ptkwt@aracnet.com\> wrote:  
> > \> Amidst all of the discussion about the alioth benchmarks and how  
> > \> they are (insert disparaging term here) there was a little  
> > \> discussion about the Ackermann benchmark and how Ruby finishes  
> > \> dead last even behind gawk(in fact doesn't finish for values of N  
> > \> larger than 6).
> > 
> > [snipped benchmark]
> > 
> > \> Well, that's simple enough. Nothing to improve there and  
> > \> essentially looks like the Python version, except that the python  
> > \> version includes:  
> > \>  
> > \> import sys  
> > \> sys.setrecursionlimit(5000000)  
> > \>  
> > \> ....kind of handy that they can do that from within their program.
> > 
> > This is a bit of a cheat, IMO, to do this within Python. I suspect  
> > that it could be done within Ruby, but I think that Matz had  
> > indicated that this is more appropriately an operating system  
> > function. Indeed:
> > 
> > &nbsp;&nbsp;austin@austin:~$ time ack.rb 7  
> > &nbsp;&nbsp;Ack(3,7): 1021
> > 
> > &nbsp;&nbsp;real 0m1.258s  
> > &nbsp;&nbsp;user 0m1.230s  
> > &nbsp;&nbsp;sys 0m0.010s
> > 
> > &nbsp;&nbsp;austin@austin:~$ ulimit -s 16384  
> > &nbsp;&nbsp;austin@austin:~$ time ack.rb 8  
> > &nbsp;&nbsp;Ack(3,8): 2045
> > 
> > &nbsp;&nbsp;real 0m5.306s  
> > &nbsp;&nbsp;user 0m5.250s  
> > &nbsp;&nbsp;sys 0m0.030s
> > 
> > &nbsp;&nbsp;austin@austin:~$ time ack.rb 9  
> > &nbsp;&nbsp;Ack(3,9): 4093
> > 
> > &nbsp;&nbsp;real 0m22.707s  
> > &nbsp;&nbsp;user 0m22.520s  
> > &nbsp;&nbsp;sys 0m0.150s  
> > &nbsp;&nbsp;austin@austin:~$ ruby -v  
> > &nbsp;&nbsp;ruby 1.8.2 (2005-03-10) [i686-linux]
> > 
> > Thus, by changing ulimit in the user level, I can do the Ackermann  
> > test. That is a linode, by the way, with 96 Mb of memory. Comparing  
> > like to like, I get:
> > 
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;7 8 9  
> > Python 0.643 3.071 11.519  
> > Python-s DNF DNF DNF  
> > Python-u DNF DNF DNF  
> > Ruby 1.234 DNF DNF (1933 levels)  
> > Ruby-u 1.210 5.319 23.275  
> > Perl 0.835 3.659 20.935
> > 
> > Python-s removes the setrecursion limit; Python-u does the same but  
> > changes ulimit. IN REALITY, we see that Python -- without this  
> > setting change -- can't even finish Ack(3,7). (The variance in the  
> > test table above and my earlier results is that they were run at  
> > different times.)
> > 
> > Ruby, on the other hand, does finish it with this OS setting. I  
> > suspect that the stack frames (bindings) in Ruby are larger, which  
> > explains the speed difference to some degree. Could Ruby be faster?  
> > We're pretty competitive with Perl there. Probably. I wouldn't know  
> > the first thing about speeding it up -- or if we really need to.
> > 
> > \> So the conclusion is that Ruby isn't so great at recursion (not a  
> > \> new conclusion). If you're looking for a language that's good for  
> > \> recursion (because you like that style of programming or whatever)  
> > \> then looking at the results of this benchmark would be  
> > \> informative. You could tell right away that Ruby isn't a good  
> > \> choice for that style of programming. One might dismiss this by  
> > \> saying "well, I never use recursion anyway", but a lot of  
> > \> algorithms are much easier to implement recusively (algorithms  
> > \> which deal with walking trees for example).
> > 
> > But it would be an incorrect assumption -- remember, I changed a  
> > userspace OS-level value from 8192 (the default stack size in  
> > kilobytes) to 16384, and was able to do ack(3,9). It blew up on  
> > ack(3, 10) -- but I can't change the stack any larger. However, we  
> > went from blowing up around 1500 levels to 4500 levels of recursion.
> > 
> > This is \*part\* of the reason that I have significant issues with the  
> > alioth shootout. They don't take any responsibility for these  
> > numbers or understanding the nature of problems -- and seem to be  
> > proud of it. They've accepted a Perl version that goes for fast-and-  
> > ugly:
> > 
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# in our quest for speed, we must get ugly:  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# it helps reduce stack frame size a little bit  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# from Leif Stensson  
> > &nbsp;&nbsp;&nbsp;&nbsp;sub Ack {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return $\_[0] ? ($\_[1] ? Ack($\_[0]-1, Ack($\_[0], $\_[1]-1))  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;: Ack($\_[0]-1, 1))  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;: $\_[1]+1;  
> > &nbsp;&nbsp;&nbsp;&nbsp;}
> > 
> > All because it's "prettier but slower to do this":
> > 
> > &nbsp;&nbsp;&nbsp;&nbsp;sub Ack {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;my($M, $N) = @\_;  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return( $N + 1 ) if ($M == 0);  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return( Ack($M - 1, 1) ) if ($N == 0);  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Ack($M - 1, Ack($M, $N - 1));  
> > &nbsp;&nbsp;&nbsp;&nbsp;}
> > 
> > IMO, this is completely inappropriate. If the Perlers are going to  
> > do things to reduce their stack frames, and the Pythonistas are  
> > going to muck around with recursion limits that help their code run  
> > at all ... why can't Rubyists reduce or eliminate the recursion  
> > entirely?
> > 
> > -austin  
> > --  
> > Austin Ziegler \* halostatue@gmail.com  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\* Alternate: austin@halostatue.ca

---

<div class="post-metadata">

**Author:** ![Christian\_Neukirche1](https://avatars.discourse-cdn.com/v4/letter/c/ee7513/32.png) [@Christian\_Neukirche1](https://rubytalk.org/u/Christian_Neukirche1)\
**Post date:** [14 June 2005 19:38 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/4 "2005-06-14T19:38:16Z")

</div>

Austin Ziegler \<halostatue@gmail.com\> writes:

> IMO, this is completely inappropriate. If the Perlers are going to  
> do things to reduce their stack frames, and the Pythonistas are  
> going to muck around with recursion limits that help their code run  
> at all ... why can't Rubyists reduce or eliminate the recursion  
> entirely?

The real question is why the Ruby interpreter doesn't do tail-call  
optimization...

> **···**
>
> > -austin
> 
> --  
> Christian Neukirchen \<chneukirchen@gmail.com\> [http://chneukirchen.org](http://chneukirchen.org)

---

<div class="post-metadata">

**Author:** ![Alan\_Chen3](https://avatars.discourse-cdn.com/v4/letter/a/85f322/32.png) [@Alan\_Chen3](https://rubytalk.org/u/Alan_Chen3)\
**Post date:** [14 June 2005 20:00 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/5 "2005-06-14T20:00:31Z")

</div>

Austin Ziegler wrote:

> IMO, this is completely inappropriate. If the Perlers are going to  
> do things to reduce their stack frames, and the Pythonistas are  
> going to muck around with recursion limits that help their code run  
> at all ... why can't Rubyists reduce or eliminate the recursion  
> entirely?

I think it depends on the purpose of the ackermann benchmark. If its  
there to get a reading on how fast you perform a given algorithm  
(ackermann) then eliminating the recursion would be entirely  
appropriate. If its there to try to compare how well different  
languages recurse, then its not really appropriate. Honestly, I think  
its there to benchmark recursion performance by executing a known  
complexity recursion algorithm. Although I would argue that Python and  
Perl should be judged on both a "naive" and "optimized" ackermann  
benchmarks.

> **···**
>
> > On 6/14/05, Phil Tomson \<ptkwt@aracnet.com\> wrote:

---

<div class="post-metadata">

**Author:** ![Ptkwt](https://avatars.discourse-cdn.com/v4/letter/p/f14d63/32.png) [@Ptkwt](https://rubytalk.org/u/Ptkwt)\
**Post date:** [14 June 2005 22:05 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/6 "2005-06-14T22:05:32Z")

</div>

In article \<9e7db91105061411595a036a81@mail.gmail.com\>,

> > Amidst all of the discussion about the alioth benchmarks and how  
> > they are (insert disparaging term here) there was a little  
> > discussion about the Ackermann benchmark and how Ruby finishes  
> > dead last even behind gawk(in fact doesn't finish for values of N  
> > larger than 6).
> 
> [snipped benchmark]
> 
> > Well, that's simple enough. Nothing to improve there and  
> > essentially looks like the Python version, except that the python  
> > version includes:  
> > =20  
> > import sys  
> > sys.setrecursionlimit(5000000)  
> > =20  
> > ....kind of handy that they can do that from within their program.
> 
> This is a bit of a cheat, IMO, to do this within Python. I suspect  
> that it could be done within Ruby, but I think that Matz had  
> indicated that this is more appropriately an operating system  
> function. Indeed:
> 
> austin@austin:~$ time ack.rb 7  
> Ack(3,7): 1021
> 
> real 0m1.258s  
> user 0m1.230s  
> sys 0m0.010s

Definately doesn't run for me on my laptop.

> austin@austin:~$ ulimit -s 16384  
> austin@austin:~$ time ack.rb 8  
> Ack(3,8): 2045

Doesn't work either.

> real 0m5.306s  
> user 0m5.250s  
> sys 0m0.030s
> 
> austin@austin:~$ time ack.rb 9  
> Ack(3,9): 4093
> 
> real 0m22.707s  
> user 0m22.520s  
> sys 0m0.150s  
> austin@austin:~$ ruby -v  
> ruby 1.8.2 (2005-03-10) [i686-linux]
> 
> Thus, by changing ulimit in the user level, I can do the Ackermann  
> test. That is a linode, by the way, with 96 Mb of memory. Comparing  
> like to like, I get:
> 
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;7 8 9  
> Python 0.643 3.071 11.519  
> Python-s DNF DNF DNF  
> Python-u DNF DNF DNF  
> Ruby 1.234 DNF DNF (1933 levels)  
> Ruby-u 1.210 5.319 23.275  
> Perl 0.835 3.659 20.935
> 
> Python-s removes the setrecursion limit; Python-u does the same but  
> changes ulimit. IN REALITY, we see that Python -- without this  
> setting change -- can't even finish Ack(3,7). (The variance in the  
> test table above and my earlier results is that they were run at  
> different times.)
> 
> Ruby, on the other hand, does finish it with this OS setting.

Again, not on my box. Ruby 1.8.2, Debian linux, PIII 650 256MB RAM. It  
would appear to be very sensitive to the kind of machine you're running  
on (not surprising, of course).

On my desktop machine I just tried it and found that it would finish for  
7 without changing the ulimit, but not for 8. I then set the ulimit as  
you did above and it finished for both 8 and 9.

> I  
> suspect that the stack frames (bindings) in Ruby are larger, which  
> explains the speed difference to some degree. Could Ruby be faster?  
> We're pretty competitive with Perl there. Probably. I wouldn't know  
> the first thing about speeding it up -- or if we really need to.
> 
> > So the conclusion is that Ruby isn't so great at recursion (not a  
> > new conclusion). If you're looking for a language that's good for  
> > recursion (because you like that style of programming or whatever)  
> > then looking at the results of this benchmark would be  
> > informative. You could tell right away that Ruby isn't a good  
> > choice for that style of programming. One might dismiss this by  
> > saying "well, I never use recursion anyway", but a lot of  
> > algorithms are much easier to implement recusively (algorithms  
> > which deal with walking trees for example).
> 
> But it would be an incorrect assumption -- remember, I changed a  
> userspace OS-level value from 8192 (the default stack size in  
> kilobytes) to 16384, and was able to do ack(3,9). It blew up on  
> ack(3, 10) -- but I can't change the stack any larger. However, we  
> went from blowing up around 1500 levels to 4500 levels of recursion.
> 
> This is \*part\* of the reason that I have significant issues with the  
> alioth shootout. They don't take any responsibility for these  
> numbers or understanding the nature of problems -- and seem to be  
> proud of it. They've accepted a Perl version that goes for fast-and-  
> ugly:
> 
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# in our quest for speed, we must get ugly:  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# it helps reduce stack frame size a little bit  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# from Leif Stensson  
> &nbsp;&nbsp;&nbsp;sub Ack {  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return $\_[0] ? ($\_[1] ? Ack($\_[0]-1, Ack($\_[0], $\_[1]-1))  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;: Ack($\_[0]-1, 1))  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;: $\_[1]+1;  
> &nbsp;&nbsp;&nbsp;}

Well, could we do something similar? If it's allowed, then why not? It's  
still tesing recursion.

> All because it's "prettier but slower to do this":
> 
> &nbsp;&nbsp;&nbsp;sub Ack {  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;my($M, $N) =3D @\_;  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return( $N + 1 ) if ($M =3D=3D 0);  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return( Ack($M - 1, 1) ) if ($N =3D=3D 0);  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Ack($M - 1, Ack($M, $N - 1));  
> &nbsp;&nbsp;&nbsp;}
> 
> IMO, this is completely inappropriate. If the Perlers are going to  
> do things to reduce their stack frames, and the Pythonistas are  
> going to muck around with recursion limits that help their code run  
> at all ... why can't Rubyists reduce or eliminate the recursion  
> entirely?

We could try to submit an iterative version and see if it gets accepted  
😉

If we could 'muck around with recusion limits' as they do in Python, then  
we should put that in the benchmark code. But I don't think there is any  
'built-in' way of doing this.

Phil

> **···**
>
> Austin Ziegler \<halostatue@gmail.com\> wrote:
> 
> > On 6/14/05, Phil Tomson \<ptkwt@aracnet.com\> wrote:

---

<div class="post-metadata">

**Author:** ![Glenn\_Parker1](https://avatars.discourse-cdn.com/v4/letter/g/ba8739/32.png) [@Glenn\_Parker1](https://rubytalk.org/u/Glenn_Parker1)\
**Post date:** [15 June 2005 03:42 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/7 "2005-06-15T03:42:40Z")

</div>

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/&gt](http://www.tetrafoil.com/&gt);

---

<div class="post-metadata">

**Author:** ![Isaac\_Gouy1](https://avatars.discourse-cdn.com/v4/letter/i/4bbf92/32.png) [@Isaac\_Gouy1](https://rubytalk.org/u/Isaac_Gouy1)\
**Post date:** [14 June 2005 21:05 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/8 "2005-06-14T21:05:32Z")

</div>

Alan Chen wrote:  
-snip-

> Although I would argue that Python and Perl should be judged on both a "naive"  
> and "optimized" ackermann benchmarks.

Me too.

---

<div class="post-metadata">

**Author:** ![George\_Ogata1](https://avatars.discourse-cdn.com/v4/letter/g/d9b06d/32.png) [@George\_Ogata1](https://rubytalk.org/u/George_Ogata1)\
**Post date:** [15 June 2005 11:04 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/9 "2005-06-15T11:04:06Z")

</div>

Christian Neukirchen \<chneukirchen@gmail.com\> writes:

> The real question is why the Ruby interpreter doesn't do tail-call  
> optimization...

Wouldn't this be tricky in the general case? Consider:

&nbsp;&nbsp;def f arg  
&nbsp;&nbsp;&nbsp;&nbsp;(class \<\< arg; self; end).send(:define\_method, :f){|a| 10}  
&nbsp;&nbsp;&nbsp;&nbsp;f(1)  
&nbsp;&nbsp;end

`f' looks tail recursive but isn't since it may redefine itself:

&nbsp;&nbsp;f(self)

We could just sweep the problem under the rug (optimize anyway and  
hope no-one tries anything that crazy). Or we could resort to a new  
keyword, say `recurse(...)', which would mean "call the function it  
appears in". That would be optimizable.

Just a thought.

---

<div class="post-metadata">

**Author:** ![Pit](https://avatars.discourse-cdn.com/v4/letter/p/f14d63/32.png) [@Pit](https://rubytalk.org/u/Pit)\
**Post date:** [16 June 2005 14:34 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/10 "2005-06-16T14:34:20Z")

</div>

Christian Neukirchen \<chneukirchen \<at\> gmail.com\> writes:

> The real question is why the Ruby interpreter doesn't do tail-call  
> optimization...

The interpreter doesn't do this automatically. You have to tell him 🙂

&nbsp;&nbsp;class TCOTest

&nbsp;&nbsp;&nbsp;&nbsp;# tail-recursive factorial  
&nbsp;&nbsp;&nbsp;&nbsp;def fact( n, acc = 1 )  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if n \< 2 then acc else fact( n-1, n\*acc ) end  
&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;&nbsp;# length of factorial  
&nbsp;&nbsp;&nbsp;&nbsp;def fact\_size( n )  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;fact( n ).size  
&nbsp;&nbsp;&nbsp;&nbsp;rescue  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$!  
&nbsp;&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;end

&nbsp;&nbsp;t = TCOTest.new

&nbsp;&nbsp;# normal method  
&nbsp;&nbsp;puts t.fact\_size( 10000 ) # =\> stack level too deep

&nbsp;&nbsp;# enable tail-call optimization  
&nbsp;&nbsp;class TCOTest  
&nbsp;&nbsp;&nbsp;&nbsp;tailcall\_optimize :fact  
&nbsp;&nbsp;end

&nbsp;&nbsp;# tail-call optimized method  
&nbsp;&nbsp;puts t.fact\_size( 10000 ) # =\> 14808

Here's the missing code, based on an idea from Sam Stephenson in  
[ruby-talk:113700]

&nbsp;&nbsp;class Class  
&nbsp;&nbsp;&nbsp;&nbsp;def tailcall\_optimize( \*methods )  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;methods.each do |meth|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;org = instance\_method( meth )  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;define\_method( meth ) do |\*args|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if Thread.current[meth]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;throw( :recurse, args )  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Thread.current[meth] = org.bind( self )  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result = catch( :done ) do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;loop do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;args = catch( :recurse ) do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;throw( :done, Thread.current[meth].call( \*args ) )  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Thread.current[meth] = nil  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end

Note that this is just a proof of concept and hasn't been tested thoroughly.

Regards,  
Pit

---

<div class="post-metadata">

**Author:** ![Christian\_Neukirche1](https://avatars.discourse-cdn.com/v4/letter/c/ee7513/32.png) [@Christian\_Neukirche1](https://rubytalk.org/u/Christian_Neukirche1)\
**Post date:** [15 June 2005 14:59 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/11 "2005-06-15T14:59:34Z")

</div>

George Ogata \<g\_ogata@optushome.com.au\> writes:

> Christian Neukirchen \<chneukirchen@gmail.com\> writes:
> 
> > The real question is why the Ruby interpreter doesn't do tail-call  
> > optimization...
> 
> Wouldn't this be tricky in the general case? Consider:
> 
> &nbsp;&nbsp;def f arg  
> &nbsp;&nbsp;&nbsp;&nbsp;(class \<\< arg; self; end).send(:define\_method, :f){|a| 10}  
> &nbsp;&nbsp;&nbsp;&nbsp;f(1)  
> &nbsp;&nbsp;end
> 
> `f' looks tail recursive but isn't since it may redefine itself:
> 
> &nbsp;&nbsp;f(self)

So what? It just calls the new definition with a TC and it's  
done... It can simply detect on each function \*definition\* whether it  
is going to use TCO.

> We could just sweep the problem under the rug (optimize anyway and  
> hope no-one tries anything that crazy). Or we could resort to a new  
> keyword, say `recurse(...)', which would mean "call the function it  
> appears in". That would be optimizable.

Please don't try to copy Forth, that is a bad idea in general. 🙂

> **···**
>
> > Just a thought.
> 
> --  
> Christian Neukirchen \<chneukirchen@gmail.com\> [http://chneukirchen.org](http://chneukirchen.org)

---

<div class="post-metadata">

**Author:** ![Christian\_Neukirche1](https://avatars.discourse-cdn.com/v4/letter/c/ee7513/32.png) [@Christian\_Neukirche1](https://rubytalk.org/u/Christian_Neukirche1)\
**Post date:** [16 June 2005 14:57 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/12 "2005-06-16T14:57:37Z")

</div>

Pit Capitain \<pit@capitain.de\> writes:

> Christian Neukirchen \<chneukirchen \<at\> gmail.com\> writes:
> 
> > The real question is why the Ruby interpreter doesn't do tail-call  
> > optimization...
> 
> The interpreter doesn't do this automatically. You have to tell him 🙂

I know that, but there is no reason it couldn't... while your code  
surely is a nice hack, it's nowhere close to the real thing.

> **···**
>
> > Note that this is just a proof of concept and hasn't been tested thoroughly.
> > 
> > Regards,  
> > Pit
> 
> --  
> Christian Neukirchen \<chneukirchen@gmail.com\> [http://chneukirchen.org](http://chneukirchen.org)

---

<div class="post-metadata">

**Author:** ![Logan\_Capaldo](https://avatars.discourse-cdn.com/v4/letter/l/7ea924/32.png) [@Logan\_Capaldo](https://rubytalk.org/u/Logan_Capaldo)\
**Post date:** [15 June 2005 16:02 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/13 "2005-06-15T16:02:24Z")

</div>

you do-whatever-mean?  
ok.

😉

> **···**
>
> On 6/15/05, Christian Neukirchen \<chneukirchen@gmail.com\> wrote:
> 
> > Please don't try to copy Forth, that is a bad idea in general. 🙂
> 
> > Christian Neukirchen \<chneukirchen@gmail.com\> [http://chneukirchen.org](http://chneukirchen.org)

---

<div class="post-metadata">

**Author:** ![George\_Ogata1](https://avatars.discourse-cdn.com/v4/letter/g/d9b06d/32.png) [@George\_Ogata1](https://rubytalk.org/u/George_Ogata1)\
**Post date:** [16 June 2005 11:34 UTC](https://rubytalk.org/t/ruby-and-recursion-ackermann-benchmark/18969/14 "2005-06-16T11:34:41Z")

</div>

Christian Neukirchen \<chneukirchen@gmail.com\> writes:

> George Ogata \<g\_ogata@optushome.com.au\> writes:
> 
> > Christian Neukirchen \<chneukirchen@gmail.com\> writes:
> > 
> > > The real question is why the Ruby interpreter doesn't do tail-call  
> > > optimization...
> > 
> > Wouldn't this be tricky in the general case? Consider:
> > 
> > &nbsp;&nbsp;def f arg  
> > &nbsp;&nbsp;&nbsp;&nbsp;(class \<\< arg; self; end).send(:define\_method, :f){|a| 10}  
> > &nbsp;&nbsp;&nbsp;&nbsp;f(1)  
> > &nbsp;&nbsp;end
> > 
> > `f' looks tail recursive but isn't since it may redefine itself:
> > 
> > &nbsp;&nbsp;f(self)
> 
> So what? It just calls the new definition with a TC and it's  
> done... It can simply detect on each function \*definition\* whether it  
> is going to use TCO.

Yeah, that is kind of obvious now that you say it. In fact, now that  
I read your words again, I realize you said "tail-call" and nothing  
about tail recursivity. I was way off.

Apologies.
