Tail-call optimization for Ruby
🔖 Tags
🗎 File Tree
⌥ Branches [master]
Clone URL
Latest Commits
2023-07-06 Update homepage — 🔖 v1.0.0
2019-01-27 Increment version — 🔖 v0.0.2
2019-01-27 Add required ruby version
2019-01-27 Add LICENSE
2019-01-27 Updates for initial release — 🔖 v0.0.1
2019-01-27 Refactor tests
2019-01-27 Move functions into module
2019-01-26 Use rake to run tests
More...
Tail call optimization for mutually (indirectly) and directly recursive functions in Ruby.
The current design uses a trampoline. However, it is implemented in a way that still allows a tail recursive function to easily return a Proc as its terminal value.
examples
require 'mutual_recursion'
include MutualRecursion
def mutual_one(x, y = 0)
return terminal_value(y) if x.negative?
tail_call { mutual_two(x, y + 1) }
end
def mutual_two(x, y)
tail_call { mutual_one(x - 1, y) }
end
mutual_one(50_000).invoke
# => 50001
require 'mutual_recursion'
include MutualRecursion
def direct(x, y = 0)
return terminal_value(y) if x.negative?
tail_call { direct(x - 1, y + 1) }
end
direct(50_000).invoke
# => 50001
require 'mutual_recursion'
include MutualRecursion
def proc_returning(x, y = 0)
return terminal_value(proc { "|#{y}|" }) if x.negative?
tail_call { proc_returning(x - 1, y + 1) }
end
generated_proc = proc_returning(20).invoke
generated_proc.call
# => "|21|"
require 'mutual_recursion'
def without_include(x, y = 0)
return MutualRecursion.terminal_value(y) if x.negative?
MutualRecursion.tail_call { without_include(x - 1, y + 1) }
end
without_include(50_000).invoke
# => 50001