Chapter 22 · Part V — Applied Recurrence

Algorithms That Preserve State

#Opening signal

Chapter 5 showed that the naive recursive Fibonacci is exponentially slow purely because it forgets — it recomputes the same subterms billions of times. The fix, memoization, was nothing but preservation: remember each result the first time you compute it. This is not a Fibonacci trick; it is one of the central ideas in all of algorithm design, and it is the method of this book expressed in code. This chapter shows how Attempt, Preserve, and Validate appear, under other names, throughout the algorithms that make computing tractable.

#Mathematical core

FACT. Dynamic programming is the discipline of solving a problem by preserving the solutions to its subproblems, so that each subproblem is solved once and reused. It applies exactly when a problem has optimal substructure (its solution is built from solutions to subproblems) and overlapping subproblems (the same subproblems recur) — which is precisely the situation of the Fibonacci recurrence.^[55] Memoization is top-down dynamic programming: keep the recursive structure but cache results. Tabulation is bottom-up: fill a table from the base cases upward, which is exactly the iterative Fibonacci of Chapter 5. Both convert exponential recomputation into linear work by preserving intermediate state.

FACT. Streaming algorithms take preservation to its opposite extreme: when you cannot preserve everything (the data is too large to store), you preserve a carefully chosen summary — enough state to answer the question, no more. The iterative Fibonacci is itself a stream processor: it preserves only the two-value state $s_{n}$ and discards the rest, computing the sequence in constant memory. Matrix exponentiation (Chapter 5) preserves structure rather than values, using the Q-matrix to leap logarithmically. Across all these, the design axis is the same: what is the minimal state I must preserve to take the next step correctly? — which is the Preserve beat, asked as an algorithmic question.

#Odisena translation

METHOD. Map algorithm design onto the AVPT beats. Attempt: propose a way to compute the next result, with its cost (Chapter 5's bounded attempt). Preserve: identify and keep the minimal subproblem state — the cache, the table, the streaming summary — that avoids recomputation. Validate: check the result against invariants or an independent computation before trusting it. The recurring design question "what state must I preserve?" is the Preserve beat wearing an algorithm-design hat, and it is answerable precisely: the order of the recurrence, the set of overlapping subproblems, the summary sufficient for the query.

#Boundary note

INTERPRETATION. Not every problem is a dynamic-programming problem, and forcing preservation where it does not help wastes memory for nothing. The interpretation I hold: preservation pays off exactly when subproblems overlap — when the same work would otherwise be repeated. Where subproblems are all distinct (no overlap), caching them helps nothing and costs memory. The skill is not "always preserve" but "recognize overlap," which is the algorithmic form of the general lesson: preserve what recovery or reuse will actually need, not everything.

#Applied CASE

CASE. Compute the number of ways to tile a $2 \times n$ strip with dominoes. The answer is $F_{n + 1}$ , because a tiling either ends in a vertical domino (leaving a $2 \times (n - 1)$ strip) or two horizontal dominoes (leaving a $2 \times (n - 2)$ strip) — the Fibonacci recurrence, arrived at through a counting argument.^[56] Solved naively by recursion, it is exponential. Solved by preserving subproblem counts (dynamic programming), it is linear. The same problem, the same answer, an exponential difference in cost — decided entirely by whether intermediate state is preserved. This is the book's thesis in a single algorithm: forgetting is expensive; preserving is what makes growth affordable.

#Failure mode

The failure mode is recomputation from forgetting: an algorithm that repeatedly solves the same subproblems because it preserves nothing, turning a tractable problem exponential. Its signature is the program that is correct on small inputs and hangs on large ones — the naive recursion in every guise. A second failure is over-preservation: caching non-overlapping subproblems, spending memory for no reuse. The fix is to identify overlap and preserve exactly the recurring subproblem state — the minimal cache, table, or summary — and no more.

#Reusable protocol — The State-Preservation Design Card

For any algorithm that computes results built from sub-results:

Identify the recurrence. How is a result built from sub-results?
Detect overlap. Do the same subproblems recur? (If yes, preservation pays; if no, it does not.)
Choose the minimal preserved state. The cache (memoization), the table (tabulation), or the summary (streaming) sufficient to avoid recomputation.
Bound the cost. State the time and memory of the preserving version (Chapter 5's card).
Validate. Check results against an invariant or independent method before trusting them.

#Validation questions

For your current algorithm, what is the minimal state you must preserve to take the next step?
Do your subproblems overlap — and are you preserving them, or recomputing?
Is your program correct-but-slow on large inputs, the signature of forgetting?
Are you caching anything that never gets reused?

#A second algorithmic case: streaming under a memory ceiling

CASE. Suppose you must process a stream of events far too large to store — billions of records flowing past, and you can hold only a tiny summary in memory. This is the opposite constraint from memoization (where you preserve more to save time); here you must preserve less while still answering the question. The iterative Fibonacci is the archetype: it answers "what is $F_{n}$ ?" while holding only two numbers, discarding all earlier terms, because it identified the minimal state — the adjacent pair — sufficient to take the next step. Streaming algorithms generalize this: to count distinct items in a huge stream, to estimate a running quantile, to detect a trend, you design a summary that is small, updatable in one pass, and sufficient for the query, and you prove that the summary preserves what the answer needs and safely forgets the rest. The design question is identical to Chapter 2's: what is the minimal state I must preserve to take the next step correctly? — only now the answer is constrained by a hard memory ceiling, so "minimal" becomes not a preference but a requirement. The discipline is the same discipline the whole book teaches, running under a tighter budget: preserve exactly what recovery of the answer needs, and no more, but never less.

INTERPRETATION. Between memoization (preserve more to save time) and streaming (preserve less to save space) lies the entire art of state management, and the two extremes share a single insight: the right amount to preserve is determined by the question, not by habit or fear. Preserve too little and you cannot answer; preserve too much and you drown. The skilled practitioner does not default to either hoarding or discarding — they ask what the next step and the eventual query actually require, and preserve precisely that. This is why the Preserve beat is a design act and not a storage policy: it demands that you understand your system well enough to know what its future will need, which is a far deeper form of understanding than knowing what it currently holds.

#Matrix methods and the preservation of structure

FACT. There is a third mode of preservation, distinct from both memoization (preserve values) and streaming (preserve a summary), and it is worth naming because it is the most sophisticated: preserving structure rather than data. The matrix-exponentiation method for Fibonacci (Chapter 5) does exactly this. It does not preserve the intermediate terms at all; instead it preserves the algebraic structure — the Q-matrix and the fact that its powers reproduce the sequence — and exploits that structure to leap logarithmically, doubling the index at each squaring step. Where memoization remembers what the sequence did, matrix exponentiation remembers how the sequence works and uses that knowledge to skip ahead. This is a higher form of preservation: preserving the generating rule in a form you can compute with directly, rather than preserving its outputs. It is why the method achieves $O (log n)$ where iteration achieves $O (n)$ — structural knowledge is more powerful than accumulated data when you can get it.

INTERPRETATION. The three modes of preservation form a ladder of sophistication that recurs throughout systems design. At the bottom, preserve the values (memoization, full snapshots) — simple, general, and often expensive. In the middle, preserve a sufficient summary (streaming, sampling) — cheaper, but requires understanding what the summary must capture. At the top, preserve the structure (matrix methods, closed forms, generating rules) — cheapest and most powerful, but available only when you understand the system deeply enough to capture its structure in computable form. The ladder is a ladder of understanding: the more you understand a system, the less raw data you need to preserve to reconstruct or advance it, because structural knowledge substitutes for accumulated observation. A system you understand structurally, you can regenerate from a small rule; a system you understand only empirically, you must preserve in bulk. This is one more reason the regenerate-not-patch discipline is so powerful: it presumes structural understanding — a canonical generating source — and structural understanding is what lets you keep the source small and rebuild everything else on demand.

#Bridge

Algorithms preserve state to compute affordably. Systems must preserve state to recover affordably. The next chapter scales the preservation discipline up from a single algorithm to a whole architecture — infrastructure that can roll back, replay, and reconstruct because it was built to preserve.