This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).

Challenge Notebook

Problem: Implement fibonacci recursively, dynamically, and iteratively.

Constraints
Test Cases
Algorithm
Code
Unit Test
Solution Notebook

Constraints

None

Test Cases

n = 0 -> 0
n = 1 -> 1
n > 1 -> 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

Algorithm

Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.

Code



In [ ]:

    
def fib_recursive(n):
    # TODO: Implement me
    pass



In [ ]:

    
num_items = 10
cache = [None] * (num_items + 1)


def fib_dynamic(n):
    # TODO: Implement me
    pass



In [ ]:

    
def fib_iterative(n):
    # TODO: Implement me
    pass

Unit Test

The following unit test is expected to fail until you solve the challenge.



In [ ]:

    
# %load test_fibonacci.py
from nose.tools import assert_equal


class TestFib(object):

    def test_fib(self, func):
        result = []
        for i in range(num_items):
            result.append(func(i))
        fib_seq = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
        assert_equal(result, fib_seq)
        print('Success: test_fib')


def main():
    test = TestFib()
    test.test_fib(fib_recursive)
    test.test_fib(fib_dynamic)
    test.test_fib(fib_iterative)


if __name__ == '__main__':
    main()

Solution Notebook

Review the Solution Notebook for a discussion on algorithms and code solutions.