Testing Recursion

A short post to start the new year. Let's imagine that you are building an application that requires the application of a specific algorithm, but you want to build it test first. And let's further assume that the algorithm is recursive, like a fibonacci algorithm:

module MyMath
def self.fib(n)
  if n < 3
   1
 else
  MyMath.fib(n - 1) + MyMath.fib(n - 2)
 end
end


(Uncle Bob would like me to remind you that, yes, I know that this is a terrible algorithm for fib, but it serves for this example).

The first case is easy enough:

it "returns 1 for numbers less than three" do
  fib(2).should == 1
end

…but what about the second? You could create an exhaustive set of test cases to "prove" the algorithm, but instead, we want to test the behavior of it. And in this case, what we want is that any number greater than three gets the fib method called on it. Which begs a test like:

it "splits the number and calls fib when greater" do
  MyMath.should_receive(:fib).with(3)
  MyMath.should_receive(:fib).with(2)
  MyMath.fib(4)
end

But this kind of a test won't do what it seems. RSpec intercepts the method call for verification, so the test will fail that fib was only called once - the time we called it in our test! Again - this is a *well known algorithm*, not a design being driven (This distinction matters which will be the subject of an upcoming blog post). So how do we write a test which checks if the method is called recursively?

In Ruby, we can use aliases for methods. They look like:

def x
  puts "Hi"
end

alias :y :x

y
 => "Hi"

Given this, we alias our method inside our test to allow us to create the stub RSpec needs while still calling the method to kick everything off:

 it "splits the number and calls fib when greater" do
  MyMath.class_eval do
    class << self
      alias_method :fib_not_stubbed, :fib
    end
  end
  MyMath.should_receive(:fib).with(3)
  MyMath.should_receive(:fib).with(2)
  MyMath.fib_not_stubbed(4)
 end

This modifies the module for this test only to alias the fib method to the name fib_not_stubbed. Then, when we set our expectations, RSpec stubs a method called "fib" which the code from fib_not_stubbed calls, satisfying our expectation.

Is this perfect? No, not at all. Tests like this are usually a sign of a design smell, or the need to split responsibilities. But there are times when you are working with algorithms that you want to stay as true to an implementation as you can initially that you can reach into your bag of tools for. Just don't keep it out for very long.

Cory Foy was an 8th Light Software Craftsman.