This notebook was prepared by [Donne Martin](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
Test Cases
Algorithm
Code
Unit Test

Constraints

None

Test Cases

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

Algorithm

Recursive:

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



In [1]:

    
def fib_recursive(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)



In [2]:

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


def fib_dynamic(n):
    if n == 0 or n == 1:
        return n
    if cache[n] != None:
        return cache[n]
    cache[n] = fib_dynamic(n-1) + fib_dynamic(n-2)
    return cache[n]



In [3]:

    
def fib_iterative(n):
    a = 0
    b = 1
    for _ in range(n):
        a, b = b, a + b
    return a

Unit Test



In [4]:

    
%%writefile 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()









    



Overwriting test_fibonacci.py



In [5]:

    
%run -i test_fibonacci.py









    



Success: test_fib
Success: test_fib
Success: test_fib