From: Timothy Goddard <interfecus@...>
Date: 2006-03-13T20:58:46+09:00
Subject: The benefits of tail recursion

I thought I'd share a useful little trick with the list. I've put
together a little library (27 lines for the actual implementation) that
can convert any function into a partially tail-recursive function,
without any alteration required, using a single command.

I ran a few tests on this (included with the library) to show the time
it took to step through my sample recursive function, which stepped
forward through the fibonacci sequence, returning the Nth number (where
N was chosen in advance). Tests were run separately for each one.

N = 10000
Recursive: 0.101 seconds, 22.2 MB RAM (VSZ for process, measured on
final return)
Tail Recursive: 0.132 seconds, 3.44 MB RAM

N = 15000
Recursive: 0.216 seconds, 35.6 MB RAM
Tail Recursive: 0.204 seconds, 3.71 MB RAM

N = 30000
Recursive: 0.984 seconds, 87.5 MB RAM
Tail Recursive: 0.465 seconds, 4.50 MB RAM

N = 100000
Recursive: 79.8 seconds, 579 MB RAM (warning: time is misleading due to
swapping)
Tail Recursive: 2.70 seconds, 8.49 MB RAM

As you can see, benefits in terms of memory begin immediately. Benefits
in terms of processing time take a while to realise, at about a depth
of 15000 in this example. The technique works by aliasing the method to
a random name, replacing it with a method that handles the tail
recursion, and relying on the other function to call it again.

There are a few restrictions:
  - The last action of the function must be to recurse or return the
final value
  - The function must not spawn threads internally (this should work in
threaded applications though).

Other than that, just define your method and call:

tail_recurse :my_method, max_depth

The max_depth factor is used because the library uses a continuation
internally (which is slow) so it is much faster to recurse to a fixed
depth (15 in the tests above) rather than using full tail recursion.
This will default to one, but increasing it will usually improve
performance. For examples of use, see the demonstration included with
the library.

Here's the library itself:
require 'thread'

class Module
  def tail_recurse(meth, recurse_depth = 1)
    random_name = (rand((16 ** 10) / 2) + 16 ** 10).to_s(16).to_sym;

    # Create a randomly named alias of our original method
    alias_method random_name, meth.to_sym

    # Create a new method in the place of the old one
    define_method meth.to_sym do |*args|
      return_val = nil
      if Thread.current[random_name]
        # This has been called from the recursive function
        Thread.current[random_name][:count] += 1 # Add one to the
period counter
        if Thread.current[random_name][:count] % recurse_depth == 0
          # Save our arguments and jump back using the continuation
          Thread.current[random_name][:args] = args
          Thread.current[random_name][:continuation].call
        else
          # Recurse another level
          return_val = send(random_name, *args)
        end
      else
        # This is a new call. Set up for recursion.
        Thread.current[random_name] = {}
        Thread.current[random_name][:count] = 0
        Thread.current[random_name][:args] = args
        callcc {|cont| Thread.current[random_name][:continuation] =
cont}
        return_val = send(random_name,
*Thread.current[random_name][:args])
      end
      # Clear out the recursion information
      Thread.current[random_name] = nil
      return return_val
    end
  end
end

# This is an example that will compare recursive and tail recursive
performance.

if $0 == __FILE__
  class Fibonacci
    def fib_tail(a, b, depth)
      if depth == 1
        #system('ps u -p ' + Process.pid.to_s)
        return b
      else
        return fib_tail(b, a+b, depth - 1)
      end
    end
    tail_recurse :fib_tail, 15 # Partially tail recurse (15 levels
deep)

    def fib_recursive(a, b, depth)
      if depth == 1
        #system('ps u -p ' + Process.pid.to_s)
        return b
      else
        return fib_recursive(b, a+b, depth - 1)
      end
    end
  end

  fib = Fibonacci.new

  depth = ARGV.shift
  depth ||= 15000
  depth = depth.to_i

  puts "Normal recursive: #{depth} deep"
  start_time = Time.now
  val1 = fib.fib_recursive(1,1,depth)
  difference = Time.now - start_time
  puts "Took #{difference} seconds"

  puts "Tail recursive: #{depth} deep"
  start_time = Time.now
  val2 = fib.fib_tail(1,1,depth)
  difference = Time.now - start_time
  puts "Took #{difference} seconds"

  if val1 == val2
    puts "Values Matched"
  else
    puts "ERROR: Values different"
    puts "Recursive:"
    puts val1
    puts "Tail Recursive:"
    puts val2
  end
end