I thought ruby didn't optimize tailcalls?

ruby-talk
1

Im using ruby 1.8.6 mri. and it seems to optimize tailcalls which I
have been told it doesn't. what else could be going on here?

···

###################

def factail(n, acc=1)
    if n > 0 then factail(n-1, n*acc)
    else acc end
end

irb(main):163:0> factail(10000)
factail(10000)
284625968091705451890641321 and so on...

###################

def facto(n)
    if n > 0 then n * facto(n-1)
    else 1 end
end

irb(main):164:0> facto(10000)
facto(10000)
SystemStackError: stack level too deep
  from (irb):155:in `facto'
  from (irb):155:in `facto'
  from (irb):158
  from :0
irb(main):165:0>

########################

def fact(n)
    def f(n, acc)
        if n > 0
            then f(n-1, n*acc)
            else acc
        end
    end
    f(n, 1)
end

irb(main):183:0> fact(10000)
fact(10000)
2846259680917054518 ...

also works.

2

cnb wrote:

Im using ruby 1.8.6 mri. and it seems to optimize tailcalls which I
have been told it doesn't. what else could be going on here?

With that program, factail(2000) works for me but factail(5000) bombs
out with "stack too deep". So I guess you just have a larger default
stack size than me.

Factorials generate very large Bignums which will slow things down
substantially for large numbers. I suggest you try something simpler:

  def counttail(n, acc=0)
    if n > 0 then counttail(n-1, acc+1)
    else acc end
  end

Then you can try counttail(10_000), counttail(100_000),
counttail(1_000_000) etc until you can show your stack overflowing.

If counttail(10_000_000) still works, then post your exact version of
MRI and where you got it from. Perhaps you have some sort of patched
version (although I've not come across such a patch myself)

Regards,

Brian.

···

--
Posted via http://www.ruby-forum.com/\.