### Tail call optimization in Ruby with trampolines

Posted on April 17, 2015

The idea is taken from Clojure.

``````def trampoline
f = yield
loop do
case f
when Proc
f = f[]
else
break f
end
end
end

def fact(n, acc)
if n > 0
-> { fact(n - 1, acc * n) }
else
acc
end
end

trampoline { fact(100000, 1) }
#=> 282422940796034787429342157802453551847749492609...

def fib(a, b, n)
if n > 0
-> { fib(b, a + b, n - 1)}
else
a
end
end

(0..9).map { |i| trampoline { fib(0, 1, i) } }
#=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

trampoline { fib(0, 1, 100000) }
#=> 259740693472217241661550340212759...

# Mutual recursion

def isEven(xs)
xs.empty? || -> { isOdd(xs[1..-1]) }
end

def isOdd(xs)
!xs.empty? && -> { isEven(xs[1..-1]) }
end

trampoline { isEven((0..10000).to_a) } #=> false
trampoline { isOdd((0..10000).to_a)  } #=> true
trampoline { isEven((0..10001).to_a) } #=> true
trampoline { isOdd((0..10001).to_a)  } #=> false``````

There is also a more strict approach taken from Scala, but it seems a bit heavy for Ruby:

``````class Done

def initialize(a)
@a = a
end

def result
a
end
end

def Done(a)
Done.new(a)
end

class Call

def initialize
@rest = -> { yield }
end

def result
next_r = rest[]
loop do
case next_r
when Done
break next_r.a
when Call
next_r = next_r.rest[]
end
end
end
end

def Call
Call.new {
yield
}
end

def isEven(xs)
xs.empty? ? Done(true) : Call { isOdd(xs[1..-1]) }
end

def isOdd(xs)
xs.empty? ? Done(false) : Call { isEven(xs[1..-1]) }
end

isEven((0..9999).to_a).result   #=> true
isOdd((0..9999).to_a).result    #=> false
isEven((0..10000).to_a).result  #=> false
isOdd((0..10000).to_a).result   #=> true

def fact(n, acc)
if n > 0
Call { fact(n - 1, acc * n) }
else
Done(acc)
end
end

fact(100000, 1).result
#=> 28242294079603478742934215780245355184...``````