Memoization

We want to memorize the results of previous recursive computations so the we can reuse them and save ourselves from having to redo certain recursive computations. (Time vs space tradeoff; we're using more space to save ourselves time)

Factorial Sequence

$N! = N*(N-1)!$

$1! = 1$

In [7]:
def fac(N):
    if N == 1:
        return 1
    else:
        return N*fac(N-1)
In [8]:
print([2**N for N in range(1, 11)])
print([fac(N) for N in range(1, 11)])

[2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

Fibonacci Sequence

In [ ]:
1   2   3   4   5   6   7   8   9
1   1   2   3   5   8   13  21  34

$ fib(N) = fib(N-1) + fib(N-2)$

$ fib(1) = 1$

$ fib(2) = 1$

In [9]:
def fib(N):
    if N == 1 or N == 2:
        return 1
    else:
        return fib(N-1) + fib(N-2)
In [10]:
print([fib(N) for N in range(1, 10)])

[1, 1, 2, 3, 5, 8, 13, 21, 34]

Factorial vs Fibonacci

In [19]:
def fib_slow(N, counter):
    counter[0] += 1
    if N == 1 or N == 2:
        return 1
    else:
        return fib_slow(N-1, counter) + fib_slow(N-2, counter)

counter = [0]
print(fib_slow(20, counter))
print(counter, "steps")

6765
[13529] steps
In [20]:
def fib_fast(N, counter, memory):
    """
    memory: dict{N: fib(N)}
    """
    counter[0] += 1
    if N == 1 or N == 2:
        return 1
    else:
        part1 = 0
        if N-1 in memory:
            part1 = memory[N-1]
        else:
            part1 = fib_fast(N-1, counter, memory)
        part2 = 0
        if N-2 in memory:
            part2 = memory[N-2]
        else:
            part2 = fib_fast(N-2, counter, memory)
        res = part1 + part2
        memory[N] = res
        return res
counter = [0]
print(fib_fast(20, counter, {}))
print(counter, "steps")

6765
[21] steps

Ackermann Function

$A(m, n) = \left\{ \begin{array}{cc} n+1 & m=0 \\ A(m-1, 1) & n = 0 \\ A(m-1, A(m, n-1)) & \text{otherwise} \end{array} \right\}$

In [22]:
def A(m, n, depth=0, memory = {}, do_print = True):
    if (m, n) in memory:
        return memory[(m, n)]
    if m == 0:
        res = n+1
        if do_print:
            print("  "*depth, "A({}, {}) = {}".format(m, n, res))
    elif n == 0:
        if do_print:
            print("  "*depth, "A({}, {}) = A({}, {})".format(m, 0, m-1, 1))
        res = A(m-1, 1, depth+1)
        if do_print:
            print("  "*depth, "A({}, {}) = A({}, {}) = {}".format(m, 0, m-1, 1, res))
    else:
        if do_print:
            print("  "*depth, "A({}, {}) = A({}, A({}, {}))".format(m, n, m-1, m, n-1))
        res1 = A(m, n-1, depth+1)
        if do_print:
            print("  "*depth, "A({}, {}) = A({}, A({}, {})) = A({}, {})".format(m, n, m-1, m, n-1, m-1, res1))
        res = A(m-1, res1, depth+1)
        if do_print:
            print("  "*depth, "A({}, {}) = A({}, {}) = {}".format(m, n, m-1, res1, res))
    return res

A(2, 3)

 A(2, 3) = A(1, A(2, 2))
   A(2, 2) = A(1, A(2, 1))
     A(2, 1) = A(1, A(2, 0))
       A(2, 0) = A(1, 1)
         A(1, 1) = A(0, A(1, 0))
           A(1, 0) = A(0, 1)
             A(0, 1) = 2
           A(1, 0) = A(0, 1) = 2
         A(1, 1) = A(0, A(1, 0)) = A(0, 2)
           A(0, 2) = 3
         A(1, 1) = A(0, 2) = 3
       A(2, 0) = A(1, 1) = 3
     A(2, 1) = A(1, A(2, 0)) = A(1, 3)
       A(1, 3) = A(0, A(1, 2))
         A(1, 2) = A(0, A(1, 1))
           A(1, 1) = A(0, A(1, 0))
             A(1, 0) = A(0, 1)
               A(0, 1) = 2
             A(1, 0) = A(0, 1) = 2
           A(1, 1) = A(0, A(1, 0)) = A(0, 2)
             A(0, 2) = 3
           A(1, 1) = A(0, 2) = 3
         A(1, 2) = A(0, A(1, 1)) = A(0, 3)
           A(0, 3) = 4
         A(1, 2) = A(0, 3) = 4
       A(1, 3) = A(0, A(1, 2)) = A(0, 4)
         A(0, 4) = 5
       A(1, 3) = A(0, 4) = 5
     A(2, 1) = A(1, 3) = 5
   A(2, 2) = A(1, A(2, 1)) = A(1, 5)
     A(1, 5) = A(0, A(1, 4))
       A(1, 4) = A(0, A(1, 3))
         A(1, 3) = A(0, A(1, 2))
           A(1, 2) = A(0, A(1, 1))
             A(1, 1) = A(0, A(1, 0))
               A(1, 0) = A(0, 1)
                 A(0, 1) = 2
               A(1, 0) = A(0, 1) = 2
             A(1, 1) = A(0, A(1, 0)) = A(0, 2)
               A(0, 2) = 3
             A(1, 1) = A(0, 2) = 3
           A(1, 2) = A(0, A(1, 1)) = A(0, 3)
             A(0, 3) = 4
           A(1, 2) = A(0, 3) = 4
         A(1, 3) = A(0, A(1, 2)) = A(0, 4)
           A(0, 4) = 5
         A(1, 3) = A(0, 4) = 5
       A(1, 4) = A(0, A(1, 3)) = A(0, 5)
         A(0, 5) = 6
       A(1, 4) = A(0, 5) = 6
     A(1, 5) = A(0, A(1, 4)) = A(0, 6)
       A(0, 6) = 7
     A(1, 5) = A(0, 6) = 7
   A(2, 2) = A(1, 5) = 7
 A(2, 3) = A(1, A(2, 2)) = A(1, 7)
   A(1, 7) = A(0, A(1, 6))
     A(1, 6) = A(0, A(1, 5))
       A(1, 5) = A(0, A(1, 4))
         A(1, 4) = A(0, A(1, 3))
           A(1, 3) = A(0, A(1, 2))
             A(1, 2) = A(0, A(1, 1))
               A(1, 1) = A(0, A(1, 0))
                 A(1, 0) = A(0, 1)
                   A(0, 1) = 2
                 A(1, 0) = A(0, 1) = 2
               A(1, 1) = A(0, A(1, 0)) = A(0, 2)
                 A(0, 2) = 3
               A(1, 1) = A(0, 2) = 3
             A(1, 2) = A(0, A(1, 1)) = A(0, 3)
               A(0, 3) = 4
             A(1, 2) = A(0, 3) = 4
           A(1, 3) = A(0, A(1, 2)) = A(0, 4)
             A(0, 4) = 5
           A(1, 3) = A(0, 4) = 5
         A(1, 4) = A(0, A(1, 3)) = A(0, 5)
           A(0, 5) = 6
         A(1, 4) = A(0, 5) = 6
       A(1, 5) = A(0, A(1, 4)) = A(0, 6)
         A(0, 6) = 7
       A(1, 5) = A(0, 6) = 7
     A(1, 6) = A(0, A(1, 5)) = A(0, 7)
       A(0, 7) = 8
     A(1, 6) = A(0, 7) = 8
   A(1, 7) = A(0, A(1, 6)) = A(0, 8)
     A(0, 8) = 9
   A(1, 7) = A(0, 8) = 9
 A(2, 3) = A(1, 7) = 9
Out[22]:
9
In [23]:
x = (1, 2) # A tuple in python is "immutable" and is not allowed to change
           # so we can use it as a key in a dictionary that remembers things

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-23-bc51f0ed26bd> in <module>
      1 x = (1, 2)
----> 2 x[0] = 5

TypeError: 'tuple' object does not support item assignment
In [ ]: