<jupyter_start><jupyter_text>This notebook was prepared by [<NAME>](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).  Solution Notebook  Problem: Implement fibonacci recursively, dynamically, and iteratively.* [Constraints](Constraints)* [Test Cases](Test-Cases)* [Algorithm](Algorithm)* [Code](Code)* [Unit Test](Unit-Test)  Constraints* 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?    * Either* Can we assume this fits memory?    * Yes  Test Cases* n = 0 -> 0* n = 1 -> 1* n = 6 -> 8* Fib sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...  AlgorithmRecursive:* Fibonacci is as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...* If n = 0 or 1, return n* Else return fib(n-1) + fib(n+2)Complexity:* Time: O(2^n) if recursive or iterative, O(n) if dynamic* Space: O(n) if recursive, O(1) if iterative, O(n) if dynamic  Code<jupyter_code>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]<jupyter_output><empty_output><jupyter_text>Unit Test<jupyter_code>%%writefile test_fibonacci.py
from nose.tools import assert_equal


class TestFib(object):

    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))
        assert_equal(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()
%run -i test_fibonacci.py<jupyter_output>Success: test_fib
Success: test_fib
Success: test_fib
{'fraction_non_alphanumeric': 0.12914046121593292, 'fraction_numerical': 0.026834381551362682, 'mean_word_length': 2.8986928104575163, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 12, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '133615', 'license': 'Apache-2.0', 'n_tokens_mistral': 909, 'n_tokens_neox': 804, 'n_words': 253, 'path': 'recursion_dynamic/fibonacci/fibonacci_solution.ipynb', 'repo_name': 'sophomore99/PythonInterective', 'size': '2391'}