From: Louis-Philippe <default@...>
Date: 2011-04-19T21:28:01+09:00
Subject: Re: Tail Call Optimization (Tail Recursion)

--0016e6d9a318786b6904a144a30d
Content-Type: text/plain; charset=ISO-8859-1

>
>
> I'm surprised that they are still working. Gambit Scheme takes
> very little time for this.
>
>
and they still are ;)  as I was not using the same implementation of fib...
 mine was not tail recursive:

def fib(n)
  if n > 1
    fib(n-1) + fib(n-2)
  else
    n
  end
end

opposed to the tail recursive implementation cited above:

def tail_fib n, a = 0, b = 1
 if n == 0
   b
 else
   a, b = b, a + b
   tail_fib n - 1, a, b
 end
end

the thing is the tail recursive one doesn't really yield the full sequence
as it omits the 0, and so:

fib(30)          => 832040
tail_fib(30)    => 1346269

anyway, it's not that relevant in the current scope, except that with this
tail recursive implementation it can be confirmed that MRI, Rubinius and
JRuby again fail to complete, while MacRuby does just fine.

--0016e6d9a318786b6904a144a30d--