Fibonacci Python (memoized and unmemoized)

fib.py

""" Python implementation of recursive fib with/without memoization and bottom up (with pytests) """

def fib(n):
    assert n >= 0, f"n was negative ({n})"

    # Base cases
    if n in [0, 1]:
        return n

    return fib(n - 1) + fib(n - 2)


def fib_memoized(n):
    seen = {}

    def fib(m):
        assert m >= 0, f"n was negative ({n})"

        if m in [0, 1]:
            return m

        if m in seen:
            return seen[m]

        result = fib(m - 1) + fib(m - 2)
        seen[m] = result
        return result

    return fib(n)


def fib_bottom_up(n):
    assert n >= 0, f"n was negative ({n})"

    if n in [0, 1]:
        return n

    seen = {0: 0, 1: 1}
    for i in range(2, n + 1):
        seen[i] = seen[i - 1] + seen[i - 2]

    return seen[n]


def test_fib():
    assert fib(6) == 8


def test_fib_mem():
    assert fib_memoized(6) == 8


def test_fib_bottom_up():
    assert fib_bottom_up(6) == 8

Note that I used inner function in fib_memoized which I think it cleaner than using a class or something else as wrapper.

By the way, the bottum_up approach is many problems is so much easier to understand that it's weird that we have to study all this recursive stuff for programming interviews. Sure, it helps you think (I guess) but recursive solutions also take up more memory anyway so why wouldn't we just go with bottom up?