This notebook was prepared by Donne Martin. Source and license info is on GitHub.
Recursive:
Complexity:
class Math(object):
def fib_iterative(self, n):
a = 0
b = 1
for _ in range(n):
a, b = b, a + b
return a
def fib_recursive(self, n):
if n == 0 or n == 1:
return n
else:
return self.fib_recursive(n-1) + self.fib_recursive(n-2)
def fib_dynamic(self, n):
cache = {}
return self._fib_dynamic(n, cache)
def _fib_dynamic(self, n, cache):
if n == 0 or n == 1:
return n
if n in cache:
return cache[n]
cache[n] = self._fib_dynamic(n-1, cache) + self._fib_dynamic(n-2, cache)
return cache[n]
%%writefile 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()
Overwriting test_fibonacci.py
%run -i test_fibonacci.py
Success: test_fib Success: test_fib Success: test_fib