Forum: Ruby Ruby Recursion

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
D8c4c145e3d00b1b85337cb2effb3694?d=identicon&s=25 Bob (Guest)
on 2006-05-07 19:33
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
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-05-07 20:23
(Received via mailing list)
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 Gray II
Bbc4b3fca1ae3161257a8636145b424d?d=identicon&s=25 Elliot Temple (Guest)
on 2006-05-08 02:48
(Received via mailing list)
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 Temple
http://www.curi.us/blog/
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2006-05-08 13:19
(Received via mailing list)
2006/5/8, Elliot Temple <curi@curi.us>:
> 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
51a34236538906ab994cf9f2e533d14d?d=identicon&s=25 Lou Scoras (ljscoras)
on 2006-05-08 16:07
(Received via mailing list)
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
49ab3ce5a4922b4747d1d6f330784629?d=identicon&s=25 Jake McArthur (Guest)
on 2006-05-08 19:16
(Received via mailing list)
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
481b8eedcc884289756246e12d1869c1?d=identicon&s=25 Francis Cianfrocca (Guest)
on 2006-05-09 03:45
(Received via mailing list)
Does anyone know if Ruby can optimize tail-recursions?
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-05-09 03:57
(Received via mailing list)
On May 8, 2006, at 8:44 PM, Francis Cianfrocca 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 Gray II
4b174722d1b1a4bbd9672e1ab50c30a9?d=identicon&s=25 Ryan Leavengood (Guest)
on 2006-05-09 03:57
(Received via mailing list)
On 5/8/06, Francis Cianfrocca <garbagecat10@gmail.com> wrote:
> Does anyone know if Ruby can optimize tail-recursions?

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

Ryan

1. http://www.atdot.net/yarv/
4b174722d1b1a4bbd9672e1ab50c30a9?d=identicon&s=25 Ryan Leavengood (Guest)
on 2006-05-09 04:00
(Received via mailing list)
On 5/8/06, James Edward Gray II <james@grayproductions.net> 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 ;)

Ryan
308cbef6e86dfc49cce3b2d4cf42aedc?d=identicon&s=25 SASADA Koichi (Guest)
on 2006-06-30 03:34
(Received via mailing list)
Hi,

I found this article today :)

James Edward Gray 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,
This topic is locked and can not be replied to.