Recursion in Ruby 3.2 (tail call, trampoline and TCO)

fib.rb

def fib(position)
  return position if position < 2

  fib(position - 1) + fib(position - 2)
end

def fib_tc(position, _current = 0, _next = 1)
  return _current if position < 1

  fib_tc(position - 1, _next, _current + _next)
end

def fib_tramp_tc(position, _current = 0, _next = 1)
  return _current if position < 1

  -> { fib_tramp_tc(position - 1, _next, _current + _next) }
end

def fib_trampoline(position)
  result = fib_tramp_tc(position)

  while result.is_a?(Proc)
    result = result.call
  end

  result
end

fib_10k_tc.rb

load 'fib.rb'

# This line will cause a stack overflow and the program will crash
puts "fib_tc(10000) = #{fib_tc(10000)}"

# This line will never be executed, the program crashed at line #4
puts 'Done!'

fib_10k_tco.rb

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

load 'fib.rb'

puts "fib_tc(10000) = #{fib_tc(10000)}"

puts 'Done!'

fib_10k_trampoline.rb

load 'fib.rb'

puts "fib_trampoline(10000) = #{fib_trampoline(10000)}"

puts 'Done!'

fib_benchmark.rb

require 'benchmark'
load 'fib.rb'

input = ARGV[0].to_i

Benchmark.bm do |x|
  x.report('fib') { fib(input) }
  x.report('fib_tc') { fib_tc(input) }
  x.report('fib_trampoline') { fib_trampoline(input) }
end

results_fib_30

| Function       | User Time | System Time | Total Time | Real Time  |
| -------------- | --------- | ----------- | ---------- | ---------- |
| fib            | 0.000369  | 0.000060    | 0.000429   | 0.000135   |
| fib_tc         | 0.000015  | 0.000003    | 0.000018   | 0.000012   |
| fib_trampoline | 0.000020  | 0.000003    | 0.000023   | 0.000021   |