Ruby Recursion

Ruby
1

Hi all,

I am new to Ruby, and I have only known it through rails. I was
wondering if it’s a good idea to use recursion sparingly in Ruby?
How efficiently is it implemented? Do recursive calls only store local
variables or the entire method?
Is there a maximum stack size/depth?

Thanks!

Bob

2

On May 7, 2006, at 12:34 PM, Bob wrote:

I was wondering if it’s a good idea to use recursion sparingly in
Ruby?

My opinion is, yes, it is.

How efficiently is it implemented? Do recursive calls only store
local
variables or the entire method?

I’m not aware of any recursive specific optimizations and method
calls in general are fairly expensive in Ruby.

Is there a maximum stack size/depth?

Yes and Ruby uses the C stack so it’s fairly easy to hit. I avoid
recursion unless I am reasonably sure it will not go too deep.

James Edward G. II

3

On May 7, 2006, at 10:34 AM, Bob wrote:

Hi all,

I am new to Ruby, and I have only known it through rails. I was
wondering if it’s a good idea to use recursion sparingly in Ruby?
How efficiently is it implemented?

It’s a good idea to recursion as much as you find convenient, and
then test your code and see if it’s too slow or not. If it’s too
slow, you have to figure out why, and you can put recursion on a long
list of possible reasons.

If you have a specific algorithm you are considering doing
recursively, you could easily test just that algorithm to see if it’s
fast enough.

– Elliot T.

4

2006/5/8, Elliot T. [email protected]:

then test your code and see if it’s too slow or not. If it’s too
slow, you have to figure out why, and you can put recursion on a long
list of possible reasons.

I’m more on James’ side: since recursion doesn’t really scale in Ruby
I try to avoid it where possible from the start.

13:16:04 [~]: ruby -e ‘def r(i)puts i;r i+1 end; r 0’|tail
-e:1:in r': stack level too deep (SystemStackError) from -e:1:in r’
from -e:1
12886
12887
12888
12889
12890
12891
12892
12893
12894
12895
13:16:06 [~]:

Kind regards

robert

5

I like recursion, and it’s very unfortunate that Ruby’s recursion is
pretty crappy. I say use it initially, then go to a loop-based
implementation if you overflow the stack or find that it’s too slow.
I end up doing this about 10% of the time that I use recursion.

  • Jake McArthur
6

I’m going to weigh in on Elliot’s side =) Recursive solutions for all
their sluggishness are often the most elegent and easiest to read.

For what it’s worth I would recomend:

  1. Write your test.
  2. Make it work in the dumbest possible way.
  3. Profile.
  4. Optimize as necessary.

“Premature optimization is the root of all evil.” – C. A. R. Hoare

7

On May 8, 2006, at 8:44 PM, Francis C. wrote:

Does anyone know if Ruby can optimize tail-recursions?

Not yet. I believe this is planned for YARV though, if it doesn’t
already do it.

James Edward G. II

8

Does anyone know if Ruby can optimize tail-recursions?

9

On 5/8/06, James Edward G. II [email protected] wrote:

Not yet. I believe this is planned for YARV though, if it doesn’t
already do it.

Great minds think alike. You only beat me by 1 minute :wink:

Ryan

10

Hi,

I found this article today :slight_smile:

James Edward G. II wrote:

Not yet. I believe this is planned for YARV though, if it doesn’t
already do it.

YARV can achieve tail call optimization (not on default). But not
tail recursion.

On Ruby syntax, we can’t optimize tail recursion. Because Ruby don’t
support like “Java private method”.

How about this pattern? :

class C
def fact n
n <= 2 ? 1 : n * fact(n)
end
end

class D < C
def fact n
p n
super
end
end

D.new.fact(10)

or Module#include, Object#extend, …

Regards,

11

On 5/8/06, Francis C. [email protected] wrote:

Does anyone know if Ruby can optimize tail-recursions?

Not yet, though I think YARV[1] can do it.

Ryan

  1. YARV: Yet Another Ruby VM