tail_call_optimization.rb

# Base factorial version not tail recursive
def fact(n)
  return 1 if n <= 1
  n * fact(n-1)
end

# enable tail recursive optimization
RubyVM::InstructionSequence.compile_option = {
   tailcall_optimization: true,
   trace_instruction: false
}

# Tail recursive version
RubyVM::InstructionSequence.compile(<<-EOF).eval
 def fact_tail(n, acc=1)
   return acc if n <= 1
   fact_tail(n-1, n*acc)
 end
EOF

# saves the params in a stack array
# actually is faster then the tail_recursive version
def fact_stack(val)
   res = 1
   params = [val]
   while !params.empty?
      current_param = params.delete_at(0)
      return res if current_param <= 1
      if current_param > 1
         res = current_param * res
         params << (current_param -1)
      end
   end
end

# this will print out "stack level too deep."
# fact(100000)

# now this won't stack overflow
#fact_tail(100000)

# this won't stack overflow either
#fact_stack(100000)

times = 200000
require 'benchmark'
Benchmark.bm do |x|
      #   x.report("fact: ") {fact(times) }
        x.report("fact_tail: ") { fact_tail(times)}
        x.report("fact_stack: ") { fact_stack(times)}
end