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

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 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.
  • 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

--

--

Infrastructure Support Engineer/Technical Writer (snowplow.io) with a passion for Python/writing documentation. More about me: https://pavol.kutaj.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Pavol Kutaj

Infrastructure Support Engineer/Technical Writer (snowplow.io) with a passion for Python/writing documentation. More about me: https://pavol.kutaj.com