From: Paul Battley <pbattley@...>
Date: 2006-03-14T02:31:25+09:00
Subject: Re: The benefits of tail recursion

Very nice. However, I couldn't run the normal recursed fibonacci test
beyond 1500 iterations on my machine without getting a 'stack level
too deep' error. How did you manage 100,000?

I was able to improve the performance of tail recursion quite a bit by
reducing the number of lookups:

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 (local_store = Thread.current[random_name])
       # This has been called from the recursive function
       local_store[:count] += 1 # Add one to the period counter
       if local_store[:count] % recurse_depth == 0
         # Save our arguments and jump back using the continuation
         local_store[:args] = args
         local_store[:continuation].call
       else
         # Recurse another level
         return_val = send(random_name, *args)
       end
     else
       # This is a new call. Set up for recursion.
       local_store = (Thread.current[random_name] = {})
       local_store[:count] = 0
       local_store[:args] = args
       callcc {|cont| local_store[:continuation] = cont}
       return_val = send(random_name, *local_store[:args])
     end
     # Clear out the recursion information
     Thread.current[random_name] = nil
     return return_val
   end
 end
end

This version provides gains from about 50 iterations up. I might have
accidentally broken the thread safety, though...

Paul.