# Objectives

• What is a Starter Test? When to use it?
• Focus on getting it to work first, cleanup by refactoring and then focus on optimization.
• When refactoring, start green and end in green.
• Learn recursive solution and optimize the execution by using non-recursive solution.
• Using existing tests as regression tests when making major changes to existing code.

# Problem Statement

Generate Fibonacci sequence for a given number.

# Problem Domain Analysis

In mathematics, the Fibonacci numbers are the numbers in the following integer sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 ... By definition, the first two numbers in the Fibonacci sequence are 0 and 1 and each subsequent number is the sum of the previous two.

## Algebraic Equation

In mathematical terms, the sequence fibonacci(n) of Fibonacci numbers is defined by the recurrence relation :

``````fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
``````

with seed values

``````fibonacci(0) = 0
fibonacci(1) = 1
``````

## Sample Input Output

Each input output set is an example. Make each example executable.

``````Input  : 0, 1, 2, 3, 4, 5
Output : 0, 1, 1, 2, 3, 5
``````

The final solution should be able to take any random number and calculate the Fibonacci number without any modification to the production code.

## Initial Conditions

First two numbers are given (not calculated).

# Steps

## Step 1

In this step, we set up the environment.

``````require 'test/unit'

class FibonacciTest < Test::Unit::TestCase
def test_fibonacci_of_zeror_is_zeror
fail 'fail'
end
end
``````

In this step, we got the proper require statement to execute the test. The test also follows the proper naming convention for tests. This example illustrates how to go from Requirements to Examples to Executable Specs. Each test for this problem takes an argument, does some computation and returns a result. It illustrates Direct Input and Direct Output. This is called State Based Testing. In State Based Testing, there are no side effects. Side effect free functions are easy to test.

See the appendix of the Essential TDD book for definition of Direct Input, Direct Output and Side Effects.

## Step 2

In this step, we will discover the public API. Here is the fibonacci_test.rb

``````require 'test/unit'

class Fibonacci
def self.of(number)
0
end
end

class FibonacciTest < Test::Unit::TestCase
def test_fibonacci_of_zero_is_zero
fib_of_zero = Fibonacci.of(0)
assert_equal(fib_of_zero, 0)
end
end
``````

## Starter Test

Start by testing a variant of an operation that doesn't do anything. If you write a realistic test first, then you will find yourself solving a bunch of problems at once. Realistic test will leave you too long without feedback. You want the red/green/refactor loop to take just minutes. You can shorten the loop by choosing inputs and outputs that are trivially easy to discover. Pick a Starter Test that will teach you something but that you are certain you can quickly get to work.
----- Kent Beck (Test-driven Development: By Example)

Starter Test is helpful when you are implementing something unfamiliar or complicated. You don't need the Starter Test when you are confident, you can pick a test that will require a non-trivial operation.

## Step 3

Don't change the test code and code under test at the same time.

``````require 'test/unit'

class Fibonacci
def self.of(number)
0
end
end

class FibonacciTest < Test::Unit::TestCase
def test_fibonacci_of_zero_is_zero
fib_of_zero = Fibonacci.of(0)
assert_equal(0, fib_of_zero)
end
end
``````

In this step, I found the right assertion to use. You can see the order of the parameters for assert_equal matters. I overcame the temptation to change the test code and code under test at the same time. Thereby test driving the development of the production code. I got the test to pass quickly by using a fake implementation. The fake implementation returns a constant.

## Step 4

Here is the dirty implementation that makes fib(1) = 1 pass very quickly using a dirty implementation.

``````require 'test/unit'

class Fibonacci
def self.of(number)
number
end
end

class FibonacciTest < Test::Unit::TestCase
def test_fibonacci_of_zero_is_zero
fib_of_zero = Fibonacci.of(0)
assert_equal(0, fib_of_zero)
end

def test_fibonacci_of_one_is_one
fib_of_one = Fibonacci.of(1)
assert_equal(1, fib_of_one)
end
end
``````

## Step 5

In this step, we force the implementation to change via tests. The broken test forced the implementation to change. Here is the dirty implementation that passes the test.

``````require 'test/unit'

class Fibonacci
def self.of(number)
if number == 2
return 1
else
return number
end
end
end

class FibonacciTest < Test::Unit::TestCase
# First two specs are same as before

def test_fibonacci_of_two_is_one
fib_of_two = Fibonacci.of(2)
assert_equal(1, fib_of_two)
end
end
``````

## Step 6

This step is about refactoring in the green state. The new test broke the implementation. Commented out the new test to refactor the test in green state.

``````require 'test/unit'

class Fibonacci
def self.of(number)
if number == 0
return 0
elsif number <= 2
return 1
end
end
end

class FibonacciTest < Test::Unit::TestCase

def test_fibonacci_of_zero_is_zero
fib_of_zero = Fibonacci.of(0)
assert_equal(0, fib_of_zero)
end

def test_fibonacci_of_one_is_one
fib_of_one = Fibonacci.of(1)
assert_equal(1, fib_of_one)
end

def test_fibonacci_of_two_is_one
fib_of_two = Fibonacci.of(2)
assert_equal(1, fib_of_two)
end

def xtest_fibonacci_of_three_is_two
fib_of_three = Fibonacci.of(3)
assert_equal(2, fib_of_three)
end

end
``````

## Step 7

In this step we are going to use fake implementation.

``````require 'test/unit'

class Fibonacci
def self.of(number)
if number == 0
return 0
elsif number <= 2
return 1
end
return 2
end
end

class FibonacciTest < Test::Unit::TestCase

def test_fibonacci_of_zero_is_zero
fib_of_zero = Fibonacci.of(0)
assert_equal(0, fib_of_zero)
end

def test_fibonacci_of_one_is_one
fib_of_one = Fibonacci.of(1)
assert_equal(1, fib_of_one)
end

def test_fibonacci_of_two_is_one
fib_of_two = Fibonacci.of(2)
assert_equal(1, fib_of_two)
end

def test_fibonacci_of_three_is_two
fib_of_three = Fibonacci.of(3)
assert_equal(2, fib_of_three)
end

end
``````

## Step 8

Let's now look at recursive solution. When you look at the input and output for the Fibonacci sequence:

``````Input  : 0 1 2 3
Output : 0 1 1 2
``````

We see that the pattern emerges and we see the result is the sum of previous two Fibonacci numbers. So

``````return 2
``````

is actually return 1 + 1 which from the above same data set is :

``````fib(n-1) + fib(n-2)
``````

This is the generic solution to this problem.

``````require 'test/unit'

class Fibonacci
def self.of(number)
if number == 0
return 0
elsif number <=2
return 1
end
return of(number - 1) + of(number - 2)
end
end

class FibonacciTest < Test::Unit::TestCase

def test_fibonacci_of_zero_is_zero
fib_of_zero = Fibonacci.of(0)
assert_equal(0, fib_of_zero)
end

def test_fibonacci_of_one_is_one
fib_of_one = Fibonacci.of(1)
assert_equal(1, fib_of_one)
end

def test_fibonacci_of_two_is_one
fib_of_two = Fibonacci.of(2)
assert_equal(1, fib_of_two)
end

def test_fibonacci_of_three_is_two
fib_of_three = Fibonacci.of(3)
assert_equal(2, fib_of_three)
end

end
``````

We now have the generalized solution that uses recursion.

## Step 9

Let's clean up the solution.

``````require 'test/unit'

class Fibonacci
def self.of(n)
return 0 if n == 0
return 1 if n == 1
return of(n-1) + of(n-2)
end
end

# Specs same as previous steps
``````

Before starting refactoring you must be in green state. After refactoring is done you should still be in green state. You can see that the variables are expressive of the domain.

## Step 10

Let's now add a new test that is a large number to make sure our solution is good.

``````def test_fibonacci_of_ten_is_fifty_five
fib_of_ten = Fibonacci.of(10)
assert_equal(55, fib_of_ten)
end
``````

This is a story test. It gives us the confidence that our solution is complete. So we don't have to write any more tests and we are done.

## Step 11

Let's us now optimize the solution.

``````require 'test/unit'

class Fibonacci
def self.of(n)
current, successor = 0, 1
n.times do
current, successor = successor, current + successor
end
return current
end
end

# Tests are same as before.
``````

This version illustrates using existing tests as safety net when making major changes to the code. Notice that we only focus on one thing at a time. The focus can shift from one version to the other.

Code Mutation we discussed in a previous article is also part of the TDD Cycle. Regression is one of the goals of TDD and we have seen how to use existing test suite as a safety net for catching regression bugs.

## TDD Cycle

In this example we saw how we go about repeating the TDD cycle many times to form a rhythm. We wrote a failing test, we quickly made it pass with a quick and dirty implementation and then we refactored to cleanup the code. The focus is on the design during the refactor step.

# Exercises

1) Run the mini-test based Fibonacci and sure all tests pass.

``````\$ruby fibonacci_test.rb
``````

2) Move the Fibonacci class into its own file and make all the tests pass.
3) Get the output of the mini-test in color.
4) Convert the given mini-test to rspec version fibonacci_spec.rb. You can refer the solution in the appendix of the Essential TDD book.

# Ace the Technical Interview

• Easily find the gaps in your knowledge
• Get customized lessons based on where you are
• Take consistent action everyday
• Builtin accountability to keep you on track
• You will solve bigger problems over time
• Get the job of your dreams

#### Take the 30 Day Coding Skills Challenge

Gain confidence to attend the interview

No spam ever. Unsubscribe anytime.