On Nov 14, 2007 10:33 AM, Robert Klemme <shortcutter / googlemail.com> wrote:
> 2007/11/14, Chet Nichols III <chet.nichols / gmail.com>:

> > so i started running into a problem using recursion with ruby- it seemed a
> > little too soon for me to be getting a stack overflow ('stack level too deep
> > (SystemStackError)'), so i wrote up a quick simple script to do some
> > recursion:
> >
> > -----
> > #!/usr/local/bin/ruby
> >
> > def print_depth num
> >  puts num
> >  print_depth(num+1)
> > end
> >
> > print_depth 0
> > -----
> >
> > and sure enough, once im at a recursive depth of about 4,360, it errors out.
> > i tried making num a global $num instead so it wasnt allocating memory on
> > the stack each time for building a new 'num' object, but that only got me to
> > about 4,500 until the overflow. to me, it seems a little low, especially for
> > something this simple. my stack size is 10240. and, of course, when i up it
> > to something like 20480, i get about double the recursive depth.. but when i
> > try the same thing in C:
...

> > i get a recursive depth of about 350,000 before it bombs out (which is what
> > i'd expect more or less). i know C is super efficient and all, and ruby is
> > truly object oriented, so each thing pushed on the stack is an object with
> > its own set of methods, etc, so its by design going to take up more space,
> > but i was wondering if there are any plans to do anything to help the
> > efficiency of this at all?

>
> You'll find it in the archives. This issue comes up frequently.
> Basically Ruby is not good at recursion for exactly the reason you
> discovered.

Actually this is a problem with ruby, the implementation, rather than
Ruby the language.

Two comments.

1) Just this morning I listened to a podcast interview with Evan
Phoenix and the differences between the invocation stacks in MRI and
rubinius was discussed.  Evan brought up something I hadn't thought
about. Because of the way MRI is implemented each Ruby method call
will result in multiple C stack frames, so you need to multiply the
recursion depth of that ruby program by some number to get the
equivalent C stack depth.

2) There's no good reason why a Ruby implementation couldn't do
tail-recursion optimization on the program in question, which would
make that program much closer to an IDEAL infinite loop (i.e. one
which would run out of non-cpu cycle resources much more slowly <G>)


-- 
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/