TDDing into a Fibonacci Sequence in C#

A few days ago, I mentioned how I wanted to do a bit of experimentation with a Fibonacci Sequence implementation. Before I did my experimentation, I wanted a working sequence and a set of tests to validate that. This way I would know if my refactoring broke something. [Update: here's some of that experimentation.]

So let's TDD into a Fibonacci Sequence. You can grab the code from GitHub: jeremybytes/fibonacci-tdd. There are branches to go along with each step.

Initial Project
For the initial project, I created a console application and a class library to hold my tests. I figured that I could put my Fibonacci sequence class in the console application and then move it to its own project if needed.

We'll basically be looking at 2 files. The first is "FibonacciSequence.cs", and (as mentioned) this is in the console application:

Then we have the test, "FibonacciSequenceTests.cs":

Since we're going to be writing tests to make sure we've got the sequence right, I included the first 12 Fibonacci numbers. If you're not familiar with the Fibonacci sequence, each value is determined by adding the previous 2 values. So the 6th value (8) is determined by adding the previous values of 3 and 5.

The First Test
So let's write a test for the first element in the sequence. But before we do that, I'm going to do a bit of setup.

Since I want this to be a sequence (which means IEnumerable in the C# world), I'm going to stub out the interface in our production class:

I know that this is writing code before tests. But since we know we want a sequence, it makes sense to give ourselves a framework to hang our code on. Notice that even though I've added the code for the "IEnumerable<int>" interface, we haven't included any implementation. We'll write our test first.

And here's the first test:

This creates an instance of the sequence, pulls the first value, and then checks to see that it's "1".

This tests fails (as expected):

The reason for the failure is the "NotImplementedException" that gets thrown by our class.

So let's write the very simplest code possible to get this to pass:

The "yield return" will create an enumerator for us in the background so we don't have to deal with it explicitly. For more information on IEnumerable, you can check out this article series: Next, Please! A Closer Look at IEnumerable.

This code is a bit too simple. We know that it doesn't really fulfill our sequence needs. But it does get our first test to pass:

So let's move on to the next test.

Testing the 2nd Element
Now that we've got things set up, it should be easier to write additional tests. Lets set up a test for the 2nd element in the Fibonacci Sequence:

Testing the first element of a sequence is easy. Testing the second element is a bit trickier. What I did here was use the "Take" method (one of the awesome LINQ methods) to grab the first 2 items of the sequence. Then I take the "Last" value.

But there's a problem with this test. It passes:

Yikes. That's not good. When doing TDD, I expect the test to fail until I add proper implementation code. So what's the problem?

The "Take" method will grab up to the number of values requested. In our case, the sequence only returns a single item. But "Take" doesn't care; it grabs as much as it can. Then when we ask for the "Last" value, we end up getting the only one that's there, which is the first value.

Correcting the Test
When we have a test that passes when we expect it to fail, we've either got a problem with our code or a problem with our test. In this case, the problem is with our test. "Take" is not the appropriate LINQ method to use here. Fortunately, there's another LINQ method we can use: "ElementAt":

One thing to keep in mind is that "ElementAt" uses a 0-based index. So using "1" will get us the 2nd item in the sequence.

Now our test fails:

This is better. The reason for the failure is that there is no 2nd item so "ElementAt" throws an exception.

For this implementation, we'll do something very simple:

I'm feeling like this is too simple still. But I'm also thinking that we can get a little more info to let the method take shape a little more naturally before we think about refactoring.

This is enough to get the test to pass:

So let's keep moving.

Testing the 3rd Element
Next we'll write a test for the 3rd element, which we expect will be "2":

This test fails (as expected), so let's write a bit more code:

This gets our test to pass, but it's kind of stupid to keep writing the method this way. So, I'm going to to a bit of refactoring.

Refactoring to Something a Bit More Useful
Since I see a little bit of a pattern forming here, I'm going to add a "for" loop to the implementation:

I know that this won't work for the entire sequence. But it works for the tests that we have in place right now. We'll worry about fixing this in a bit, but not until our test cases call for it.

Parameterizing the Tests
It looks like we're writing the same test over and over again. This is where I look to see if we can parameterize the test. In this case, I think it will work pretty well.

Here's a new test:

I'm using NUnit, so I can set up test cases that get passed in as parameters. For more information, take a look at this article: Parameterized Tests with NUnit.

This will plug the values of the TestCases into the parameters of the test. So in the first case, it will use "0" for the "ElementAt" call (which is the first item in the sequence) and it will use "1" as the "expected" value in the assertion.

This lets us test the first 3 elements of the sequence with a single test. And our results show the tests are passing:

Notice that the results show the parameter values plugged in. This is really useful when one (or more) of these test cases fail.

Testing the 4th Element
Testing the 4th element of the sequence is as simple as adding another test case:

This test passes without any changes to our code. And that's okay. We expect the 4th element is "3", and that's what our code returns.

It's interesting to see that the simple "for" loop that we built in the code works for 3 elements in the sequence. But we'll see it break down with the next element.

Testing the 5th Element
Adding the test case for the 5th element creates a failing test. I won't show a screen shot, but the test just has "TestCase(4,5)" added.

Now we have to do a bit of math to really implement the Fibonacci Sequence:

Like the description of the Fibonacci Sequence, I add together the previous two values. A couple of local variable hang on to those values so they can be used to calculate the next item.

With this in place, all of our tests pass.

Refactoring
The tests are passing, but I see some dead code in the implementation. We are no longer using the indexer of the "for" loop. Since we don't need the indexer, we can swap the "for" loop for a "while" loop:

I'm never a huge fan of "while(true)", but it is a good way to create an infinite sequence.

The First 12 Elements
Since we've implemented the definition of the Fibonacci Sequence, we would expect that additional tests would pass. I set up the test cases for the first 12 elements:

And all of the tests pass:

Yay!

But there's a problem.

Overflow!
I've done a lot of experimentation with the Fibonacci Sequence. (I'm not sure why it intrigues me so much.) One thing I know about it is that it will overflow a 32-bit integer pretty quickly. How quickly?

Let's set up the console application to find out. We'll add code to our console application to print out the first 50 values of the Fibonacci Sequence.

And here's the output:

As we can see, something weird starts to happen at item #47. We overflow the standard integer and end up with a negative number (since the default 32-bit integer is signed).

Testing for Overflow
Now that we know where our problem is, we can create a test for it.

This test grabs elements #46 and #47 (remember, "ElementAt" is 0-based). Then we check to make sure that #47 is greater than #46.

Since this is the pivot-point of the 32-bit integer, element #47 give us a negative value, so it is *not* greater. This means our test fails.

Fixing Overflow
To fix the overflow, we'll change from using "int" (a 32-bit integer) to using a "long" (a 64-bit integer). The code is fairly easy to update at this point.

There's also one change we need to make in our tests. The "expected" parameter type needs to be changed to "long".

With this in place, we now have all of our tests passing (including the one that checks for overflow):

And we can see our console application is behaving as expected as well:

Wrap Up
This code isn't perfect. Our implementation returns an infinite sequence (because of the "while(true)"). But even our updated code isn't infinite. After a while we'll overflow the 64-bit integer as well. So we should probably add some checks in the code for overflow and end the sequence. But I'll leave that as an exercise for you.

We've reached our goal which is to have an implementation of the Fibonacci Sequence with a set of valid tests. Now that we have this in place, we can do some experimentation with the implementation.

And with the tests in place, we'll know immediately if our experimentation breaks something. In an upcoming article, we'll look at those experiments. [Update: here's a bit of that experimentation.]

Happy Coding!