Explaining Memoization

The aim of this page📝 is to introduce memoization as a way of computing deduplication in recursive processes.

This is part of the educational quest to finish Leetcode’s Explore Card RECURSION I. See how my quest is going at THE GIST OF QUEST > Leet Code > Explore > Recursion#1

Simple recursion can be repetitive

• Let’s look at a simple recursion of computing Fibonacci numbers, see SICP > 1b Procedure and Processes > Recursion

def fib_sim(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

• The recursion above performs lots of duplicate calculations as discussed in the same lecture

I’ve built a tree. Now, we can observe some things about this tree. We can see why this is an extremely bad way to compute Fibonacci numbers. Because to compute Fibonacci of four, I had to compute Fibonacci of two’s sub-tree twice. In fact, in order way to add one more, supposing I want to do Fibonacci of five, what I have to do then is compute Fibonacci of four plus Fibonacci of three. But Fibonacci of three’s sub-tree has already been built. This is a prescription for a process that’s exponential in time. To add one, I have to multiply by something because I take a proportion of the existing thing and add it to itself to add one more step. So this is a thing whose time complexity is an order of — actually, it turns out to be Fibonacci — of n. There’s a thing that grows exactly at Fibonacci numbers. It’s a horrible thing. You wouldn’t want to do it. T

The effectivization of recursion is called memoization

• The fix with the term “memoization” was coined by Donald Michie (of Bletchley Park) in 1968
• Is derived from the Latin word “memorandum” (“to be remembered”), usually truncated as “memo” in American English
• “turning [the results of] a function into something to be remembered”.
• While “memoization” might be confused with “memorization” (because they are etymological cognates), “memoization” has a specialized meaning in computing.

Use the example of fibonacci number to see how memory can be used to exit early and avoid repetition

• Take a hash table to keep track of the result of each F(n) with n as a key
• That hash serves as a cache protecting from repetitive work
• It trades time for space

cache = {}
def fib(n):
    if n in cache:
        return cache[n]
    if n < 2:
        result = n
    else:
        result = fib(n-1) + fib(n-2)
    cache[n] = result
    return result

— Visualized @ Python Tutor