TDD Beyond Basics : Factorial Kata
Compute factorial of a given number n, where n >= 0.
Problem Domain Analysis
Factorial is defined as follows:
n! = 1 x 2 x 3 x ... n for n >= 1
Given that 0! = 1
Solution Domain Analysis
We observe a pattern, so we can rewrite 4! as :
4! = 3! x 4 if n = 4, n! = (n-1)! x n
We can rewrite the examples as :
Step 1 : 0! = 1 Step 2 : 1! = 1 x 0! Step 3 : 2! = 2 x 1! Step 4 : 3! = 3 x 2! Step 5 : 4! = 4 x 3!
You can make these examples executable. Numbers cannot be negative. If the contract is broken you raise an exception. This problem lends itself to writing specs directly from the examples. We did not have to come up with a well ordered sequence of test cases before we start writing the tests.
- Take the input number n
- Treat 0! as a special case
while less than n products has been calculated, repeatedly do a) Increment index count b) Compute the product for current index by multiplying index by the current product end Return the result
In our case the class name will be Factorial. Create a file called
factorial_spec.rb with the following contents:
describe Factorial do it '0 factorial is 1' do factorial = Factorial.new(0) result = factorial.calculate expect(result).to eq(1) end end
The describe() is a rspec method. It takes a class name in this case, Factorial as the parameter.
Run the spec.
Define an empty Factorial class at the top of the
factorial_spec.rb as follows:
class Factorial end
When you run the spec, you will get error related to constructor argument. Change the Factorial class as follows:
class Factorial def initialize(n) @n = n end end
Now you get an error due to undefined method 'calculate'. Let's define the method now as follows:
class Factorial def initialize(n) @n = n end def calculate end end
You see an error 'expected 1 got nil'. We are now failing for the right reason.
Return a hardcoded 1 from the calculate method.
class Factorial def initialize(n) @n = n end def calculate 1 end end
Now we are green.
We went from no code at all (missing calculate method) to code that returns nil. This is the very first transformation in the Transformation Priority Premise transformations list. Then we went from nil to constant. This is the second transformation from TPP transformations list. We also discovered the public API for the Factorial class.
Let's write a executable spec for the second example that we came up with in the solution domain analysis section. Add the second spec as follows:
describe Factorial do # first test same as before it '1 factorial is 1' do factorial = Factorial.new(1) result = factorial.calculate expect(result).to eq(1) end end
The test passes. It's obvious why, we still have fake implementation that returns 1.
Let's add the third spec as follows:
describe Factorial do # first two tests same as before it '2 factorial is 2' do factorial = Factorial.new(2) result = factorial.calculate expect(result).to eq(2) end end
This fails with expected 2 got 1 error.
How can we make the new spec pass without making the old ones fail? Change the implementation as follows:
def calculate if @n == 0 1 else @n end end
All specs pass.
We transformed our code from no conditional to splitting the execution path by using if-else construct. This transformation is somewhere in the middle of the TPP transformations list.
Let's add the next spec as follows:
describe Factorial do # first three tests same as before it '3 factorial is 6' do factorial = Factorial.new(3) result = factorial.calculate expect(result).to eq(6) end end
The test fails with the error 'expected 6 got 3' message.
Solution 1 : We can use recursion and use the formula we came up with by recognizing the pattern. Formula for recursive solution:
n! = (n-1)! x n
Solution 2 : We can use our algorithm we developed earlier:
while less than n products has been calculated, repeatedly do a) Increment index count b) Compute the product for current index by multiplying index by the current product end return the result
The terminating condition is that we reach 1 as we reduce the number by 1 inside the loop. The initial value of the result is set to 1. Here is the pseudocode:
result = 1 while n > 1 do result = result * n n = n - 1 end
Change the implementation as follows:
class Factorial def initialize(n) @n = n end def calculate if @n == 0 1 else result = 1 while @n > 1 do result = result * @n @n = @n - 1 end result end end end
All specs pass.
Let's cleanup the code as follows:
class Factorial def initialize(n) @n = n end def calculate result = 1 while @n > 1 do result = result * @n @n = @n - 1 end result end end
You can now see that the if-else became a while construct. This is in the bottom of the TPP transformations list. While is much more generic construct than if-else. We no longer need a special case to handle the 0!. The boundary case is handled by the initial condition. If you observe the changes that happened in the above steps, you can see how Robert Martin's insight 'As the tests get more and more specific, the code gets more and more generic' is true in our case.
- Change the implementation to use recursive solution. Make sure all tests pass. Watch out for the common mistake of forgetting terminating condition for recursive solution.
- Watch the Factorial screencast or download Factorial screencast
- Write the following contract test.
it 'should raise exception for negative numbers'
You can implement it by using the following code:
raise ArgumentError, 'Negative number is not allowed' if number < 0