Tensions in Practice: Minimal retained state in tension with repeated subproblem work¶
Pure recursive calculation · one request
Define F(0)=0 and F(1)=1; every larger F(n) adds F(n−1) and F(n−2). Computing F(4) directly unfolds repeated smaller problems: F(2) is evaluated twice and F(1) three times. Saving each computed result lets later branches reuse it. There are no concurrent callers or changing inputs here; repetition arises inside one recurrence.
Retain little reusable state
Avoid keeping a keyed result table after each subproblem returns.
Avoid repeated evaluations
Compute an already-solved smaller instance only once during this request.
Why these aims pull against each other
Sharing collapses repeated occurrences in the call tree into the same retained subproblem. The retained table and its lookups cost memory and bookkeeping even when the calculation is small.
Choose an arrangement to see what changes and what remains difficult.
Finite illustrative comparisons. Text states carry the meaning; color is not a measured score or universal preference.
What this choice protects
What it costs
When it fits
Compare the arrangements
Recompute each branch
Evaluate both smaller calls each time they occur, retaining only ordinary temporary call state and the returned answer.
| Value | Evaluated | Saved? | |
|---|---|---|---|
| F(0) | 0 | 2 | No |
| F(1) | 1 | 3 | No |
| F(2) | 1 | 2 | No |
| F(3) | 2 | 1 | No |
| F(4) | 3 | 1 | No |
- What it protects
- No reusable keyed table is created or managed.
- What it costs
- Nine function-body evaluations occur in this F(4) calculation, including repeated base cases.
- When it fits
- Fits tiny or infrequently used recurrences when table management would cost more than the avoided work.
Illustration note: The finite setting and values are editorial assumptions, not measured effects or recommended operating settings. Evaluations count body executions, including base cases; temporary stack and arithmetic state still exist.
Save each result
Start with an empty request-local table; store every result including base cases. Later matching arguments return the saved result.
| Value | Evaluated | Saved? | |
|---|---|---|---|
| F(0) | 0 | 1 | YesFor reuse |
| F(1) | 1 | 1 | YesFor reuse |
| F(2) | 1 | 1 | YesFor reuse |
| F(3) | 2 | 1 | YesFor reuse |
| F(4) | 3 | 1 | YesFor reuse |
- What it protects
- Only five distinct bodies are evaluated; the mathematical values and final answer 3 remain unchanged.
- What it costs
- Five key/value records are retained through completion, and every call checks the table.
- When it fits
- Fits when repeated subproblems are costly enough and argument identity fully determines the result.
Illustration note: The finite setting and values are editorial assumptions, not measured effects or recommended operating settings. Cache hits are calls but not body evaluations. This finite table is never evicted during the request.
What this illustration does—and does not—establish
Recursion: Memoization Trade-Off supplies the recurrence-dependent reuse trade. The related mechanism bounds safe reuse to inputs that determine the result.
- The toy is pure and deterministic, so reuse cannot observe hidden changes or skip intended side effects.
- Counts describe this exact top-down recurrence and caching policy, not all ways to compute Fibonacci numbers; an iterative two-value method is another design.
- The table records retained results, not byte sizes, peak stack use or measured speed.
Source entries
Recursion
Recursion: Memoization Trade-Off supplies the conflict examined here.
Memoization Trade-Off
Recursive definitions can recompute the same subproblems exponentially many times (e.g., Fibonacci without memoization). Memoization (caching results) can reduce exponential time to polynomial, but requires additional memory and careful management of cached state.
Memoization Cache
Supplies the purity boundary for reusing a result keyed by its arguments.
When it helps, and when it misleads
Its failure mode is caching a function that is not actually pure — one whose output depends on hidden or changing state — so the cache serves confident, authoritative-looking stale answers.