From: Lou Vanek <vanek@...>
Date: 2006-03-14T02:32:26+09:00
Subject: Re: The benefits of tail recursion

do you know whether it's possible to do Ackermann with this?




Timothy Goddard wrote:

> 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