A recursion that works too hard
Start with the friendliest recursive definition in all of computing: the Fibonacci numbers, where F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1. Translated straight into code, it is two lines and obviously correct — you can read it off the definition without thinking. And yet for n around 40 it crawls, and for n around 90 it would not finish in your lifetime. The definition is fine; the way the recursion executes it is the disaster, and pinning down exactly why is the whole point of this guide.
To see the trouble, do not just run the code — draw it, exactly as the recursion-tree method from the last rung taught you. Each call to F(k) branches into a call to F(k-1) and a call to F(k-2), each of those branches again, and so on until you hit F(1) or F(0). The shape that grows is a tree of calls, and the running time is just the number of nodes in that tree. So the real question is not 'how deep is the recursion' but 'how many calls does it make in total' — and the answer is shocking.
Look at the call tree and count the repeats
Expand the tree for F(5) by hand. At the top sits F(5); below it F(4) and F(3); below F(4) sit F(3) and F(2); and so on. Now look closely and the scandal jumps out: F(3) is computed twice, F(2) three times, F(1) five times. The recursion has no memory — when the left branch already worked out F(3) from scratch, the right branch comes along later and works out the very same F(3) from scratch all over again, completely unaware. This phenomenon — distinct branches of the recursion needing the answer to the same smaller instance — is exactly what we mean by overlapping subproblems.
F(5)
|-- F(4)
| |-- F(3)
| | |-- F(2)
| | | |-- F(1)
| | | +-- F(0)
| | +-- F(1)
| +-- F(2) <-- F(2) again
| |-- F(1)
| +-- F(0)
+-- F(3) <-- the WHOLE F(3) subtree, recomputed
|-- F(2) <-- F(2) yet again
| |-- F(1)
| +-- F(0)
+-- F(1)
distinct values needed: F(0..5) -> only 6
calls actually made: 15 (and it doubles each step up)Counting precisely makes the waste undeniable. The number of calls to compute F(n) grows like F(n) itself, which is roughly 1.618^n — so the work is exponential in n. Meanwhile, how many genuinely different questions are ever asked? Only F(0), F(1), up to F(n) — that is n+1 distinct subproblems. We are paying an exponential amount of work to answer a linear number of distinct questions. Every excess call is a re-answer of a question already settled. That gap between 'calls made' and 'distinct subproblems' is the slack that dynamic programming exists to recover.
The fix in one sentence, and why it is allowed
The cure is almost insultingly simple to state: remember each answer the first time you compute it, and never compute it twice. Keep a table indexed by the subproblem; before recomputing F(k), look it up; if it is already there, return it instantly. Suddenly each of the n+1 distinct subproblems is solved exactly once, the exponential tree collapses to a linear amount of work, and F(90) returns in a blink. That is the entire idea — but stating the cure is not the same as understanding why it is safe, and the why is what separates a trick from a method.
It is safe because of a property we will lean on for the rest of this rung: the answer to a subproblem does not depend on how you got there or what surrounds it. F(3) is F(3) no matter which branch of the tree asked for it. This is the deeper sibling of overlapping subproblems, called optimal substructure: the solution to a problem is built out of the solutions to its subproblems, and those sub-solutions are themselves correct in isolation. Because F(3)'s value is context-free, caching it once and reusing it everywhere cannot possibly give a wrong answer — it gives the same value the recursion would have recomputed.
When overlap is real, and when it is a mirage
It is tempting to conclude that every recursion repeats work, but that is false, and the contrast is worth feeling. Run the same call-tree exercise on merge sort from the divide-and-conquer rung: it splits an array into two halves and recurses, but the left half and the right half are different arrays. No subproblem is ever asked twice; each node of its recursion tree is a fresh, never-seen instance. That is why a divide-and-conquer recursion can already be efficient with nothing cached at all — there is no repeated work to recover.
So the diagnostic question is precise: as the recursion branches, do different branches ever land on the identical subproblem? With Fibonacci, F(k) is identified by a single number k that lives in a small range 0..n, so collisions are forced — the pigeonhole guarantees branches must reuse the same k. With merge sort the subproblem is identified by a sub-array that is unique to its path, so collisions never happen. The presence of overlap is a property of how the subproblems are named: when distinct paths can name the same subproblem, you have overlap; when every path names something new, you do not.
Where this rung is heading
You have now met the founding observation in its purest form, and the rest of this rung is the engineering that follows from it. There are two ways to make sure each subproblem is solved once. The first keeps the natural recursion but bolts a cache onto it, returning a stored answer on the second request — that is top-down memoization, the subject of the next guide, and it is the gentlest step from the slow recursion you already wrote. The second throws the recursion away and fills the table directly in a careful order, smallest subproblem first — that is bottom-up tabulation.
From there the skills compound: naming the state precisely, writing the transition that builds a bigger answer from smaller ones, choosing an evaluation order so each entry is ready before it is needed, and finally reconstructing the actual solution — not just its cost — by tracing back through the table. With those tools in hand, the canonical hard-looking problems of the next rung — the 0/1 knapsack, the longest common subsequence, the edit distance between two strings — all fall to the same disciplined idea you just saw rescue Fibonacci.
One honest caveat before you go: collapsing exponential to linear is the dramatic case, but dynamic programming does not make everything cheap, only as cheap as the number of distinct states times the work per state. If a problem genuinely has exponentially many distinct subproblems — not repeats, but truly different ones — then no caching saves you, because there is nothing to reuse. Dynamic programming is powerful precisely when the count of distinct subproblems is small; its limits are exactly the limits of that count.