Fake tail recursion in Ruby without relying on tail optimization support in the Ruby VM

computes_recursively.rb

# This is a mixin module that adds support for tail-recursive
# style programming in Ruby without relying on any true tail
# recursion optimization in the Ruby virtual machine.
#
# Since tail recursion calls are actually deferred until after
# returning from the method that invoked #tail, recursions can
# be "nested" to an unlimited depth without overflowing the
# stack.
#
# The including module can define tail-recursive methods within
# a .recursively do ... end block.
#
# Each method must explicitly invoke tail recursion by calling
# #tail, not by calling itself by name.  A procedure must still
# invoke any non-tail recusions by calling itself by name.
# This is similar to the tail recursion pattern used in Clojure.
#
# The distinction between #tail and #<self> calls for tail and
# non-tail recursion is not enforced, so it is the programmer's
# responsibility to make the right calls in the right
# circumstances.
#
# Known limitations:
# 1. Methods defined within the #recursively block are executed
#    as instance methods of a separate class, and have no access
#    to methods defined outside of the block (could maybe work
#    around that with auto-delegation).
# 2. Mutual recursion can be done, but requires care and
#    understanding. The #recur method always recurs to the
#    method that was invoked first.
module ComputesRecursively

  # Magic return value from #tail calls.
  Recur = Object.new.freeze

  # Initialize tail-recursion support when mixed in.
  def self.included(other)
    other.extend ModuleMethods

    # Each including module gets its own RecursionComputer subclass.
    other.const_set :RecursionComputer, Class.new(self::RecursionComputer)
  end

  # Module methods added to the including module.
  module ModuleMethods
    # This method is to be invoked with a block argument from within
    # the declaration of a class or module that has included
    # ComputesRecursively.
    # Within the block, any methods that are defined can take
    # advantage of tail-recursion support.
    def recursively(&b)
      comp_class = self::RecursionComputer
      methods_were = comp_class.instance_methods

      comp_class.class_eval &b

      (comp_class.instance_methods - methods_were).each do |name|
        define_method name do |*args|
          comp_class.new(name, args).compute
        end
      end
    end
  end

  # A RecursionComputer instance is responsible for processing the
  # "nested" call sequence for a call to a tail-recursive method.
  # Each tail-recusive method is actually defined within a module's
  # RecursionComputer subclass, and is then accessed indirectly
  # through a wrapper instance method of the including class/
  # module.
  class RecursionComputer
    # Record the method name and arguments for the initial
    # invocation.
    def initialize(method, args)
      @method, @args = method, args
    end

    # Perform the recursive computation.
    def compute
      result = Recur
      result = send(@method, *@args) while result == Recur
      result
    end

    # Record the new arguments for the referred recursive call,
    # and return the special Recur constant value for subsequent
    # return to the recursive method caller (#compute).
    def tail(*args)
      @args = args
      Recur
    end
  end
end


module RecursionDemo
  extend (module ModuleMethods ; self ; end)

  module ModuleMethods
    include ComputesRecursively

    recursively do

      def greatest_common_divisor(x, y)
        # Uncomment the following line to see the iterations.
        # p [x, y]
        y == 0 ? x : tail(y, x % y)
      end

      def factorial(n, m=1)
        # Uncomment the following line to see the iterations.
        # p [n, m]
        n < 2 ? m : tail(n-1, m*n)
      end

    end
  end
end

puts RecursionDemo.greatest_common_divisor(525, 315)
# => 105
#
# Steps are...
# [525, 315]
# [315, 210]
# [210, 105]
# [105, 0]

puts RecursionDemo.factorial(9)
# => 362880
#
# Steps are...
# [9, 1]
# [8, 9]
# [7, 72]
# [6, 504]
# [5, 3024]
# [4, 15120]
# [3, 60480]
# [2, 181440]
# [1, 362880]