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