A recursive route-cost search keeps re-asking identical sub-route queries - what does memoizing the call change about its total work?
answer
- the same call, asked many times
- repetition carries no information
- work follows distinct keys
- call-tree size becomes key-space size
- depth of recursion is unchanged
basics
~20 sIt collapses the work from the number of calls the recursion makes to the number of distinct arguments it ever asks about. Each distinct query is computed once; every repeat becomes a table hit, which is what turns a branching explosion into a bounded count.
solid answer
~50 sWithout a memo, the work is the size of the call tree: a branching search re-asks the same sub-route from many different paths, and the count grows with the branching factor raised to the depth. With a memo, the work becomes the number of **distinct** arguments, because each key is computed once and every later request for it is a table hit. Purity is what licenses this - a repeated call with the same arguments is provably redundant, so skipping it cannot change any result. Concretely, if the search asks `cheapest(stop, destination, budget)` with `k` stops and a budget up to `b`, there are at most `k * (b + 1)` distinct keys however many times the recursion asks. What does not change is the answer, or the cost of the first query for each key.
code
pseudocode · 7 linesfunction cheapest(from, to, budget)
if from = to return 0
if budget = 0 return infinity
best = infinity
for each next in onward_legs(from)
best = min(best, leg_cost(from, next) + cheapest(next, to, budget - 1))
return bestgo deeper
Hold the idea: the search keeps asking the same question, and a table lets it answer each distinct question once. After that, every repeat is a read rather than a recomputation.
Be able to count it. Without a table the work follows the call tree, which grows with branching factor to the power of the depth; with one it is bounded by the number of distinct argument tuples the search can reach.
Show judgment about when it applies: arguments drawn from a small set, a branching call structure, and a function of its arguments alone. Say what it leaves untouched - recursion depth, the first search's cost, and the memory the table now holds.
The trade to own is whether to bound work with a table whose size grows with the reachable key space, or to cut the key space itself - coarser budgets, fewer distinguishing arguments - which lowers both the computation and the memory at a cost in precision.
## Where the repeated work comes from A branching search over routes reaches the same intermediate question along many different paths. Asking for the cheapest way onward from a given stop with a given remaining budget is a question that recurs every time the search arrives at that stop by any route. The recursion has no memory, so it re-derives the same answer each time, and the number of those derivations grows with the branching: with an average of `d` onward legs from each stop and a budget of `b` steps, the call tree can hold on the order of `d` to the power of `b` nodes. Notice what is being repeated. It is not similar work - it is the **same call with the same arguments**, made many times. ## What purity licenses The search step is a function of its arguments: the current stop, the destination, the remaining budget. Nothing else influences its result. That gives two guarantees the collapse depends on: - a second call with the same arguments **must** return what the first returned, so the repetition carries no information; - returning a stored value in place of the call changes nothing observable, because the call had nothing to observe - no write, no read of anything mutable. So the redundancy is not merely likely, it is provable, and removing it is not an approximation. This is the difference between memoizing a pure search and "caching" an impure one, where a second call might legitimately differ and skipping it would change the result. ## Counting the collapse State the parameters explicitly. Let `k` be the number of stops, `b` the maximum remaining budget, and `d` the average number of onward legs per stop. The destination is fixed for the whole search, so it contributes nothing to the key count. | | computations performed | what bounds it | |---|---|---| | without a memo | up to `d` to the power of `b` | the shape of the call tree | | with a memo | at most `k * (b + 1)` | the number of distinct keys | The second row is the whole point: **once the memo is in place, the count of computations is bounded by how many different questions exist, not by how many times they are asked.** Every call beyond the first for a key resolves to a table read. For even modest `d` and `b` the two rows differ by orders of magnitude. Two consequences follow: 1. The bound holds however wastefully the recursion is written. You can leave the branching structure exactly as it is; the memo puts a ceiling on the work regardless. 2. If the search only ever reaches a fraction of the possible keys, you compute only that fraction - the table fills on demand rather than in advance. ## What it does not change - **The answer.** Every result is identical to the unmemoized version. That is precisely the guarantee purity provides. - **The cost of the first query for a key.** A memo makes the second demand cheap, never the first, so the very first full search still does all the distinct work. - **The memory profile.** You have exchanged repeated computation for a table whose size grows with the distinct keys reached. On a search with a wide key space that table is the new constraint. - **The recursion depth.** Memoizing removes repeated calls, not nesting. A recursion deep enough to exhaust the call stack is still deep enough after memoizing, because the first descent along the longest path happens exactly as before. ## Recognising the pattern The signals that this collapse is available are specific: the function is a function of its arguments alone; its arguments come from a comparatively small set; and the call structure branches so that the same argument tuple arises along different paths. When all three hold, memoizing is the smallest possible change - one table, one lookup at the top of the function, one store before each return - that turns an explosion into a bounded count. When arguments barely repeat, the same change buys nothing at all, which is why "does this key recur?" is the question to answer before adding the table.
- Why is this collapse sound rather than an approximation that usually works?Because the step is a function of its arguments alone. A repeated call must return what the first returned, and substituting the stored value is invisible to the rest of the program since the call reads and writes nothing else. Skipping a repeat therefore cannot change any result - it removes work that was provably redundant, not work that was probably redundant.
- The memoized search still exhausts the call stack on a long route. Why did memoizing not help?Memoizing removes repeated calls, not nesting. The first descent along the longest path recurses exactly as deep as before, because no key on that path has been computed yet. Depth is a separate problem with separate remedies; the memo only bounds how many distinct computations happen, not how deep any single one goes.
- When does adding this table buy nothing?When the arguments barely repeat. If almost every call arrives with a tuple never seen before, the number of distinct keys is close to the number of calls, so there is no redundancy to remove - you pay for a probe and a stored entry on every call and still perform every computation. Check that the key recurs before adding the table.
saying these in an interview costs you the question
- Says memoizing changes the answers the search returns.
- Claims the first full search also gets faster.
- Thinks memoizing removes recursion depth as well as repeats.
- Assumes any recursive function benefits from a memo table.
- Ignores that the table's size grows with the distinct keys reached.
- Believes the collapse is a heuristic rather than a guarantee.