Where it runs
1. The problem
You wrote a simple recursion. It gives the right answer. Then you run it on a slightly bigger input, and it thinks for ten seconds. There is no bug in it. The recursion just solves the same small problem again and again.
Take Fibonacci numbers: fib(n) = fib(n-1) + fib(n-2). To get fib(30), the calls spread out into a huge tree: 2,692,537 calls in all. fib(5) alone is computed 121,393 times in it. Every branch redoes work another branch has already done. Add just 2 to n, and there are about 2.6 times as many calls.
The time goes into the repeats. If you answer each different question once and remember the answer, everything runs fast.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedfib(5)| n=2 | n=3 | n=4 | n=5 | |
|---|---|---|---|---|
| memo |
Compute fib(5). Plain recursion asks for the same fib(n) many times. memo stores each answer the first time it is found.
Bars: how many times fib(i) was actually computed, i from 0 to 17. A call answered from the memo computes nothing, so its bar stays put.
One operation is one call, and an answer read from the memo counts as one. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(2ⁿ)O(n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- recursive calls repeat the same arguments (overlapping subproblems)
- plain recursion is correct but too slow / exponential blow-up
- small number of distinct states even though the recursion tree is huge
- cache/memo the result of (i, ...) before returning
- Fibonacci / climbing stairs / grid-path wording with a hint to cache
Looks similar, isn't
- Recursion
Plain recursion recomputes a repeated argument every time. The cache is the entire difference.
- Dynamic programming (1-D)
Bottom-up DP fills a table in a fixed order. This fills it on demand, from the top down.
- Hash set / map
The cache is usually a map. This page is about deciding when to keep one.
- Backtracking
Backtracking explores paths that all differ, so nothing repeats. A cache there stores keys never asked again.
Cost is the number of distinct arguments times the work per call. A cache of 1e6 keys is fine.
On LeetCode
Counting problems where a plain recursion asks the same question many times, such as ways to climb stairs or to cross a grid. Save each answer in a memo the first time and reuse it.
ways(n) = ways(n minus 1) + ways(n minus 2), which is Fibonacci with different starting values.
The lesson's fib with three earlier terms instead of two, kept in the same memo.
The lesson's gridPaths under another name, memoized by the cell.
At each house choose the better of skipping it or robbing it and jumping two ahead, memoized by the index.