A Glimpse at Tail Call Recursion

Tail recursion is where a method calls itself. When I first saw tail call recursion I was blown away by it! I found it difficult to wrap my mind around. Thinking about it was like thinking about a snake eating its own tail and I couldn’t see that working out. But, as it turns out, tail call recursive methods can simplify things… you only need to gain some understanding about it.

The first thing I would recommend for learning about tail recursion is to watch Aja Hammerly‘s video “A World Without Assignment”.

She does an excellent job solving possible coin combinations as she refactors her way through the entire demonstration. This is probably my favorite thing about writing tail recursive methods is that it will really make you refactor often! IMHO tail recursive practices are the best ways to practice refactoring.

When might it be useful? When you want to perform the same actions and break something into a smaller components, following a path, following a tree, ancestry, and many similar situations work well. Now I’m no where near an expert on this, but I have now written three different tails recursive methods.

You can find plenty of blogs online about tail recursion, and they’re pretty much guaranteed to show a demonstration using the Fibonacci series. I will not be using the Fibonacci series as you can simply find an example online anywhere.

The first tail recursive method I wrote I called path finder. The idea is “given a set of ordered alphabetical character pairs, find a working path from a to z.” I posted my method on a gist: Path Finder and I asked for input and advice from people on Twitter. The method works great, and Danny Guinther gave some excellent tips which you can see on the gist.

The easiest on the eyes tail recursive method I’ve written so far is for removing empty & nil hash entries as deep as the hashes may go. Here’s the code for that.

class Hash
  def deep_compact
    delete_if {|k,v|
      if v.is_a? Hash
        v.deep_compact.empty?
      else
        v.nil?
      end
    }
  end
end

Here I’m defining a method on the Hash class so all Hash objects will now have this method. So when I have a hash like this {:a => nil} I can call the method deep_compact to clean it up: {:a => nil}.deep_compact # => {} . Here’s a result for multiple nested hashes.

x = {:a=>{:b=>2, :c=>3}, :d=>nil, :e=>{:f=>nil}, :g=>{}}
# => {:a=>{:b=>2, :c=>3}, :d=>nil, :e=>{:f=>nil}, :g=>{}} 
x.deep_compact
# => {:a=>{:b=>2, :c=>3}}

The way this method works is by going over each object within the Hash when the delete_if method is called. Anything that returns true will be removed from the Hash. The delete_if block is handed the key and value for each item in the Hash labelled by k and v. We’re only interested in what the values are so we check the value for either an empty Hash or nil. If it is either an empty Hash or nil we return true for that item we’ve iterated over and delete_if will remove it. In case you’re wondering what delete_if is operating on, it’s operating on an instance of self; which is the current Hash that you called the method deep_compact on. Lastly if the item we’re looking at an item that happens to be a Hash we go ahead and call the same method, deep_compact, on it. That is a tail recursive call. All that does is hand the inner Hash to this same method and evaluates the inner Hash in exactly the same way.

Now there are general good practices when implementing a tail call method. I’m not an authority on this, but what I do know is you want to make sure the work doesn’t grow in size, nor should it infinitely loop. So generally you hand a subset of the Object being evaluated to the next part of the process with the same method. This way you’ll eventually get to an end (in theory).

Now I’ve seen a few times that whenever tail recursive discussions are brought up some one will talk about using the languages built-in option to optimize the code efficiency of it. In Ruby it’s not enabled by default, but you can turn it on. The downside to that is you lose your stack trace info. Personally I don’t see why I would want to use this optimization. Writing a tail call method just makes repeating the same work a lot less code. I used to try to write code that could crawl all the way down a dataset without calling itself… the code becomes insanely complex and isn’t guaranteed to work. When you have the method call itself when certain conditions are met then you’ve wired it to build itself out as far as need be. So I like to use tail recursive methods for their efficiency in design and effort and I honestly don’t see a need for me to use the language optimization and lose my stack traces.

It took me a while before I wrote this article because I was heavily working on my gem PolyBelongsTo. I’ve implemented a tail recursive method in it to clone database records as deep as the children go. This took about 20 hours of thinking and refactoring to implement for me. At least 3 rewrites on the method itself. But it now works and I’m quite proud of it. Here’s the recursive method from it:

def self.pbt_deep_dup_build(item_to_build_on, item_to_duplicate)
  pbt_dup_build(item_to_build_on, item_to_duplicate)
  PolyBelongsTo::Pbt::Reflects[item_to_duplicate].each do |ref|
    child = eval("item_to_duplicate.#{ref}")
    core  = "item_to_build_on.#{PolyBelongsTo::Pbt::CollectionProxy[item_to_build_on, item_to_duplicate]}"
    if child.respond_to?(:build)
      child.each do |obj|
        eval(core).pbt_deep_dup_build(obj)
      end
    else
      eval(core).pbt_deep_dup_build(child)
    end
  end
  item_to_build_on       
end

The method first takes the current database record and duplicates it with the pbt_dup_build method and builds it, it then goes over each child record that exists for it and calls itself with pbt_deep_dup_build if any exist. My next plan for PolyBelongsTo is to add a database hierarchy mapping to it which will allow finding recursive database records and help the record duplication not worry about infinite loops. Feel free to review the code on the project!

If you’re interested in a thorough look at tail call optimization for Ruby you can read up on it at Danny Guinther’s article “Tail Call Optimization in Ruby: Deep Dive”

Summary

Think of tail call methods like cloning your efforts of work. It’s like a genetic clone of effort to work on a subset of the work that needs to be done. I’m no expert on this practice. Heck I tried writing an example here and I failed right off the bat… I would have had to refactor it many times before I got it right. So I went with one I’ve done before. For me it’s both simple and complicated. But I enjoy the art of its design and all that it helps accomplish. I highly recommend practising tail recursive methods if for no other reason than that it leads you to practice refactoring.

I hope this writing was both informational and enjoyable to you. Please feel free to comment, share, subscribe to my RSS Feed, and follow me on twitter @6ftdan!

God Bless!
-Daniel P. Clark

Image by Dave Spindle via the Creative Commons Attribution-NonCommercial 2.0 Generic License.