LearnViz CompSci
Home / Learn / Programming Fundamentals / Memoization

Advanced Topic 52 of 54 Programming Fundamentals

Memoization

Caching function results keyed by inputs to avoid recomputation.

How it works

Memoization stores a function's results keyed by its arguments, so repeated calls with the same inputs return the cached value instead of recomputing it. It turns exponential recursive algorithms like Fibonacci into linear ones by remembering overlapping subproblems, and is the top-down form of dynamic programming. A dictionary or array holds the cache.

Where it is used

Dynamic programming problems, expensive pure computations, parsing with packrat parsers, resolving dependencies and caching API or database results use memoization. Libraries offer decorators such as lru_cache.

Common pitfall

It is only valid for pure functions, since results depending on external state would go stale. Unbounded caches leak memory, so limit size or use eviction. Arguments must be hashable, and the cost of building cache keys may exceed the saved computation for cheap functions.

Where it fits in the course

Memoization is topic 52 of 54 in Programming Fundamentals, rated Advanced. It follows Monads. The next topic is Metaprogramming.

Practice and explore

How to study this topic

  1. Read the explanation above and restate the definition in your own words.
  2. Open the interactive lesson and answer its mini quiz.
  3. Read the common pitfall, then write a short example that avoids it.
  4. Check your understanding in the Programming Fundamentals quiz, and revisit the topic if you miss a question.

Frequently asked questions

What is Memoization?
Caching function results keyed by inputs to avoid recomputation. It belongs to Programming Fundamentals and is an advanced-level topic.
Where do people use Memoization?
Dynamic programming problems, expensive pure computations, parsing with packrat parsers, resolving dependencies and caching API or database results use memoization.
What is the most common mistake with Memoization?
It is only valid for pure functions, since results depending on external state would go stale.
What should I learn before this topic?
Start with Monads, the topic just before it in Programming Fundamentals.
How can I practice it?
Answer the mini quiz in the interactive lesson, then take the Programming Fundamentals quiz. You can also explore Recursion Tree in the Visual Lab.
Is Memoization hard to learn?
It is an Advanced topic. Expect to read the explanation more than once and to connect it with earlier topics. Working through a small example by hand helps most.
How long does it take to learn Memoization?
Most learners can read the explanation and finish the interactive lesson in under an hour. Fluency comes from applying the idea, so plan a few short practice sessions with the quiz.
Which topics are related to Memoization?
Monads, Metaprogramming, Currying and Partial Application are closely connected. The full list is in the related topics section of this page.
What should I study after Memoization?
Continue with Metaprogramming, the next topic in Programming Fundamentals.

Related topics