Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.ruby > #3121

Re: Tail Call Optimization (Tail Recursion)

Show all headers | View raw

[Note:  parts of this message were removed to make it a legal post.]

it seems like fib(50000) is not only too big for MRI ruby, but also Python
and Lua and Rubinius panic on it...

jRuby also complains but points to instructions to increase the stack...

otherways, I have MacRuby, Racket and Haskell in their tail recursive fib
solving routine, no results yet but all are still working...

2011/4/18 WJ <w_a_x_man@yahoo.com>

> 7stud -- wrote:
>
> > Terry Michaels wrote in post #993440:
> > > I did some googling to find out if Ruby supports tail call
> optimization,
> > > as I wanted to write tail-recursive functions. All posts I found
> > > indicated that 1.9 supports this, but it is not enabled by default.
> > > However, all those posts were about two years old, so I'm wondering
> what
> > > is the current situation: do I still need to upgrade to 1.9 to get that
> > > capability? Or is there something in 1.8 I can enable?
> >
> > Couldn't you test that by creating two recursive functions: one with a
> > tail call and one without, and then benchmarking them?
>
> def fib n, a = 0, b = 1
>  if n == 0
>    b
>  else
>    a, b = b, a + b
>    fib n - 1, a, b
>  end
> end
>
> 1.upto(9){|n|
>  p [n, fib(n)]
> }
>
> p fib( 50_000 )
>
>  ==>
>
> [1, 1]
> [2, 2]
> [3, 3]
> [4, 5]
> [5, 8]
> [6, 13]
> [7, 21]
> [8, 34]
> [9, 55]
> try4.rb:23:in `fib': stack level too deep (SystemStackError)
>        from try4.rb:23:in `fib'
>        from try4.rb:31
>
>
> irb(main):004:0> VERSION
> => "1.8.7"
>
>

Back to comp.lang.ruby | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Tail Call Optimization (Tail Recursion) Terry Michaels <cmhoward@frigidcode.com> - 2011-04-18 00:59 -0500
  Re: Tail Call Optimization (Tail Recursion) 7stud -- <bbxx789_05ss@yahoo.com> - 2011-04-18 12:29 -0500
    Re: Tail Call Optimization (Tail Recursion) "WJ" <w_a_x_man@yahoo.com> - 2011-04-18 18:10 +0000
      Re: Tail Call Optimization (Tail Recursion) Louis-Philippe <default@spiralix.org> - 2011-04-18 15:40 -0500
        Re: Tail Call Optimization (Tail Recursion) "WJ" <w_a_x_man@yahoo.com> - 2011-04-18 22:27 +0000
          Re: Tail Call Optimization (Tail Recursion) Louis-Philippe <default@spiralix.org> - 2011-04-19 07:28 -0500
            Re: Tail Call Optimization (Tail Recursion) "WJ" <w_a_x_man@yahoo.com> - 2011-04-20 04:12 +0000
              Re: Tail Call Optimization (Tail Recursion) "WJ" <w_a_x_man@yahoo.com> - 2011-04-20 04:30 +0000
                Re: Tail Call Optimization (Tail Recursion) Robert Klemme <shortcutter@googlemail.com> - 2011-04-20 06:37 -0500
        Re: Tail Call Optimization (Tail Recursion) Vincent Manis <vmanis@telus.net> - 2011-04-18 19:41 -0500
          Re: Tail Call Optimization (Tail Recursion) Steve Klabnik <steve@steveklabnik.com> - 2011-04-18 20:42 -0500
            Re: Tail Call Optimization (Tail Recursion) Vincent Manis <vmanis@telus.net> - 2011-04-18 21:51 -0500
              Re: Tail Call Optimization (Tail Recursion) Michael Edgar <adgar@carboni.ca> - 2011-04-18 22:12 -0500
              Re: Tail Call Optimization (Tail Recursion) Steve Klabnik <steve@steveklabnik.com> - 2011-04-19 08:48 -0500
                Re: Tail Call Optimization (Tail Recursion) Brian Candler <b.candler@pobox.com> - 2011-04-19 08:56 -0500
                Re: Tail Call Optimization (Tail Recursion) Steve Klabnik <steve@steveklabnik.com> - 2011-04-19 10:07 -0500
  Re: Tail Call Optimization (Tail Recursion) Steve Klabnik <steve@steveklabnik.com> - 2011-04-18 12:39 -0500

csiph-web