This notebook was prepared by Donne Martin. Source and license info is on GitHub.

- Does the sequence start at 0 or 1?
- 0

- Can we assume the inputs are valid non-negative ints?
- Yes

- Are you looking for a recursive or iterative solution?
- Implement both

- Can we assume this fits memory?
- Yes

- n = 0 -> 0
- n = 1 -> 1
- n = 6 -> 8
- Fib sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

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.

In [ ]:

```
class Math(object):
def fib_iterative(self, n):
# TODO: Implement me
pass
def fib_recursive(self, n):
# TODO: Implement me
pass
def fib_dynamic(self, n):
# TODO: Implement me
pass
```

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

In [ ]:

```
# %load test_fibonacci.py
import unittest
class TestFib(unittest.TestCase):
def test_fib(self, func):
result = []
expected = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
for i in range(len(expected)):
result.append(func(i))
self.assertEqual(result, expected)
print('Success: test_fib')
def main():
test = TestFib()
math = Math()
test.test_fib(math.fib_recursive)
test.test_fib(math.fib_dynamic)
test.test_fib(math.fib_iterative)
if __name__ == '__main__':
main()
```

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