Intuition The one core ideaMemoization is just plain recursion that keeps a notebook : whenever it works out the answer to a small piece of a problem, it writes that answer down so it never has to redo the work. Everything on this page exists to earn one sentence — "solve each distinct subproblem exactly once, remember it, and reuse it."
This page is self-contained: it builds every symbol and idea from nothing, so you can read it in isolation. Where a word links out (like Recursion ), that link is a place to go deeper later — you do not need it to follow this page. By the end you'll have the full mental toolkit for the "Memoization" topic.
Recall What is the "parent topic" I keep hearing about?This page is a foundations companion to a main topic note called Memoization (top-down DP) . That main note applies these ideas to real problems. Everything you need to understand memoization is defined right here — the main note is where you'll use it.
The whole topic sits on top of one idea: a rule that is written in terms of itself .
A function is a machine: you drop something in (the input ) and one thing comes out (the output ). We write fib(5) to mean "run the machine named fib on the input 5."
The picture: a box with an arrow going in (labelled 5) and an arrow coming out (labelled the answer).
Recursion is when a function's rule uses itself on a smaller input . To answer a big question, it asks the same question about a smaller piece, and keeps shrinking until the piece is so tiny the answer is obvious.
Look at the picture below. Reaching fib(5) means first reaching fib(4) and fib(3). Those in turn split again. The splitting stops only at the bottom , where the answer needs no further work.
The red boxes with a thick double border are where the machine stops splitting — the base cases .
The boxes marked with a ★ star (fib3) appear twice , and the ones marked with a ● dot (fib2) appear three times. That repetition — flagged by shape and colour so it reads even in greyscale — is the enemy the whole topic is built to kill.
Intuition Why recursion matters hereMemoization is nothing but recursion with a memory bolted on. If you don't feel comfortable with a function calling itself, everything after this is fog. (You can go deeper any time in Recursion , but this page defines all you need.)
A base case is the smallest input whose answer we just know , with no further recursion. It is the floor the recursion stands on.
Picture: the double-bordered red boxes at the bottom of the tree above — arrows go in , but no arrows come out the bottom , because the machine answers instantly.
Without a base case the machine would split forever ("to answer fib(2) I must answer fib(1) and fib(0)... and to answer those...") and crash. The base case is the STOP sign . Getting its value right is the single most error-prone part of the whole topic — a wrong base value makes a perfect recurrence produce perfect nonsense.
Definition Recurrence relationA recurrence is a rule that defines a value in terms of earlier values of the same thing , plus a base case that seeds it.
The star example is Fibonacci:
Now decode every symbol in that line:
F n F ( n )
F name of the function (like fib). Just a label for "the Fibonacci machine."n variable , a stand-in for "whichever number we're asking about." When we write n F ( n ) F n n n − 1 n − 2 smaller inputs . Since n − 1 < n toward the base case. That guaranteed shrinking is why the recursion ends.
Intuition Why a recurrence is the whole gameMemoization is a faithful transcription of a recurrence into code. No recurrence ⇒ nothing to memoize.
Why bolt a memory on at all? Because plain recursion is wildly wasteful when subproblems repeat.
The figure counts the boxes in the call tree as n
2 n ϕ n O ( ⋅ )
2 n n 2 3 = 2 × 2 × 2 = 8 explodes : 2 40 O ( something ) big-O of " — is shorthand for "the work grows roughly like this as the input gets big." O ( n ) O ( 2 n ) ϕ ≈ 1.618 golden ratio . It shows up because of how the tree actually branches — see the box below.
Common mistake "It doubles every level" is not quite rightIt's tempting to say the Fibonacci call tree doubles at each level, giving 2 n fib(n) splits into fib(n-1) and fib(n-2) — and the fib(n-2) branch is shorter , so it produces fewer descendants than the fib(n-1) branch. The tree is lopsided , not perfectly binary.
Counting the calls exactly, the number of nodes grows like ϕ n ϕ ≈ 1.618 Θ ( ϕ n ) theta of phi-to-the-n", meaning it grows exactly at that rate, not just at most). So 2 n upper bound; ϕ n exponential — the point that matters is: the work multiplies as n
Intuition The fix in one lineThe answer to fib(3) is always the same number. Computing it twice is pure waste. Write it down the first time; every later request becomes a free lookup. That is the entire justification for the topic.
The "notebook" the recursion writes in is a dictionary .
Definition Dictionary (hash map)A dictionary stores key → value pairs and can fetch the value for a key almost instantly. Think of a real dictionary: look up a word (the key), get its meaning (the value). Here we look up a subproblem (like 3) and get its answer (like 2).
Picture: a two-column table. Left column = keys, right column = stored answers. (More in Hash Maps / Dictionaries .)
Definition The cache / memoWhen we use a dictionary specifically to store already-computed answers, we call it the cache or memo (short for memoization ). In math it's written memo [ state ]
state
A state is the full description of which subproblem you're solving right now . For Fibonacci the state is a single number n. For a grid it's a pair (r, c). The state is exactly what becomes the key in the cache.
Common mistake The state must be completeIf the answer depends on two things but you key the cache by only one , two different subproblems land on the same shelf and you fetch the wrong stored answer. Picture two different questions being handed the same sticky note. The cache key must contain every variable that changes the answer .
You now own every piece. Here is the whole method , as plain step-by-step pseudocode — the "how" this page exists to earn. It's the pattern C-B-R-S: Check, Base, Recurse, Store.
Trace it on Fibonacci so the abstract steps become concrete:
fib(5) with a memo, step by step
fib(5) → not in memo, not base → needs fib(4) and fib(3).fib(4) → needs fib(3), fib(2); these bottom out at fib(1)=1, fib(0)=0 (base cases).As each answer is found it is Stored : memo fills up {2:1, 3:2, 4:3, 5:5}.
When the second branch of fib(5) asks for fib(3) again, the Check step finds it already in memo and returns 2 instantly — no re-splitting . That single lookup is what kills the blow-up from Section 3.
Mnemonic C-B-R-S — "Can Birds Really Sing?"C heck cache → B ase case → R ecurse → S tore. The classic bug is forgetting the S : always store before you return.
A memo buys speed, but it isn't free — it spends memory to save time . Name both costs honestly.
O ( 1 ) O ( 1 ) same tiny amount of time no matter how big the input is ." A dictionary lookup is O ( 1 ) 999 is no slower than for key 3.
Picture: a flat horizontal line — the cost never rises as inputs grow.
Intuition Why time collapsesOnce fib(3) is in the memo, asking for it again costs O ( 1 ) Count distinct states, not calls: there are only n + 1 0 , 1 , … , n O ( n )
Common mistake Speed isn't free — the memo eats memoryThe cache must physically store one entry per distinct state . For Fibonacci that's n + 1 O ( n ) space complexity . On top of that, the recursion's paused calls stack up, adding O ( recursion depth )
So the honest trade is: memoization spends O ( # states ) time from exponential down to linear. For huge state spaces that memory bill can itself become the bottleneck — never assume caching is cost-free.
Memoized code passes the memo around between calls, so you need one last vocabulary pair.
Definition Argument (parameter)An argument is a value you hand to a function when you call it — the 5 in fib(5). Inside the function, n is the name that holds whatever you passed.
Definition Default argumentA default argument like memo=None means "if the caller doesn't supply this, use this fallback." A common safe pattern is memo=None, then on the first line if memo is None: memo = {} — this builds a fresh empty dictionary each top-level call.
Common mistake The mutable-default trap (preview)Writing def solve(n, memo={}) creates that {} once , shared across all calls forever, so stale answers can leak between unrelated runs. That's why the safe pattern above uses memo=None. Python's built-in lru_cache decorator sidesteps this entirely by managing the cache for you.
Read this map top to bottom — it is the exact order of the sections above, showing what depends on what:
Function (Sec. 0) is the raw machine.Recursion (Sec. 0) is a function calling itself; it needs a base case (Sec. 1) to stop.Recursion that references earlier values is a recurrence (Sec. 2).
A recurrence with repeated subproblems causes the exponential blow-up (Sec. 3) — the pain.
A dictionary (Sec. 4) keyed by state (Sec. 4) gives free O ( 1 )
Combine them with the C-B-R-S algorithm (Sec. 5), mind the memory cost (Sec. 6) and the default-argument safety (Sec. 7) — and you have memoization .
Function: input to output
Recursion: function calls itself
Base case: where splitting stops
Recurrence: value from smaller values
Blow-up: repeated subproblems
State: full subproblem id
Default argument memo none
Each arrow means "the lower box uses the idea in the upper box." Trace any path to MEMOIZATION and you're retracing why each foundation had to come first.
Cover the right side and check you can answer each before moving on.
What does it mean for a function to be recursive ? It calls itself on a smaller input, shrinking toward a base case.
What is a base case and why is it essential? The smallest input whose answer is known outright; it's the STOP sign that ends the recursion.
In F ( n ) = F ( n − 1 ) + F ( n − 2 ) F ( n ) The Fibonacci machine's output for input n n
Why is plain recursive Fibonacci exponential, and what is its exact growth rate? The lopsided call tree recomputes repeated subproblems; the true node count grows like Θ ( ϕ n ) ϕ ≈ 1.618 2 n
What does O ( 1 ) Constant time — the same tiny cost regardless of input size, like a dictionary lookup.
What is a dictionary / hash map ? A store of key→value pairs with near-instant lookup by key.
What is a state in memoization? The full description of the current subproblem — it becomes the cache key.
What are the four steps of the memoized algorithm? C-B-R-S: Check cache → Base case → Recurse → Store (store before returning).
What TWO resources does memoization cost, and how much? Time drops to O ( # states ) rises to O ( # states ) O ( depth )
Why is def f(n, memo={}) dangerous? The {} is created once and shared across all calls, leaking stale cached answers between invocations.
One-sentence definition of memoization? Recursion that stores each distinct subproblem's answer in a cache so it's computed exactly once.
Recursion — the engine underneath everything hereDynamic Programming — the umbrella these ideas live underTime Complexity Analysis — where Θ ( ϕ n ) O ( n ) Hash Maps / Dictionaries — the cache's data structureDivide and Conquer — recursion without overlap (no memo needed)Tabulation (Bottom-up DP) — the iterative twin you'll meet nextlru_cache decorator — Python's built-in auto-cache 
