Recurrence Equation¶
Method — instantiates Dynamic Subproblem Reuse
The mathematical relation that expresses a subproblem's value in terms of its smaller neighbors' values — the compact engine a reuse structure evaluates.
Recurrence Equation is the mathematical relation itself: a single expression that gives a subproblem's value as a function of the values of smaller, adjacent, or later subproblems, over a defined space of states. Its defining trait is that it is an object of formulation, not a procedure — it states how a value depends on other values, and it fixes the state variable the relation ranges over and the direction in which those dependencies point. It computes nothing on its own and stores nothing; it is the compact engine that a method drives and a table records. Getting the equation right is the intellectual crux of the whole reuse structure — a correct recurrence makes the rest mechanical, and a subtly wrong one corrupts every answer downstream.
Example¶
A hydroelectric operator must decide how much water to release from a reservoir each week across a season to maximize the value of the power generated, given uncertain inflows and hard limits on how full or empty the reservoir may get. The Recurrence Equation captures the entire trade-off in one line: the best achievable value from a given reservoir level in a given week equals the immediate value of the best release now plus the best achievable value from the resulting level next week. The state is the discretized reservoir level; the equation ranges over it. The dependency direction points backward from the season's end — this week's value is defined in terms of next week's, so the relation is naturally solved by backward induction. Written down, this equation is the whole model: it says nothing about how to evaluate it or where to file the results, but it fixes, exactly and auditably, what "optimal" means at every level and every week. An operator can read the equation and see the trade being made; the arithmetic is somebody else's job.
How it works¶
- State the dependency. The equation expresses one subproblem's value as a function — a max, min, sum, or expectation — over the values of specified smaller or neighboring subproblems. This single relation is the model.
- Fix the state variable. It declares what quantity indexes a subproblem (a level, an index, a remaining budget), because the relation is only meaningful relative to the state it ranges over.
- Set the direction. It establishes which subproblems depend on which, and therefore the direction — forward or backward — in which the dependencies resolve, along with the base cases that terminate the recursion.
- Stay declarative. It asserts what must hold among the values; it does not iterate, cache, or assemble — those are for the mechanisms that consume it.
Tuning parameters¶
- State variable choice — what to make the argument of the relation. A well-chosen state makes the equation compact and correct; a poorly-chosen one either omits information the recurrence needs or smuggles in dependencies the relation can't express.
- Combination operator — whether values combine by max, min, sum, or expectation, which encodes the objective directly into the relation.
- Base cases — the terminal values that anchor the recursion; wrong or missing base cases quietly break every value that builds on them.
- Horizon and direction — finite versus infinite horizon, forward versus backward dependency, which determine how (and whether) the equation resolves to definite values.
When it helps, and when it misleads¶
Its strength is compression and auditability: a correct recurrence states an entire optimization model in one legible line, exposes the objective and the trade-off for inspection, and lets the correctness of the whole reuse structure be argued about at the level of a single relation rather than a sprawl of code.
Its failure mode is a state that doesn't capture everything the relation depends on — a recurrence that looks clean but references information its state variable doesn't carry, so the "smaller subproblems" it invokes are not actually determined, and every value computed from it is subtly wrong.[n1] The classic misuse is writing a plausible-looking equation and trusting it because it typechecks, without proving that an optimal whole really does decompose the way the relation claims. The guard is to verify that the state is a sufficient summary — that nothing outside it affects the value — and to check the base cases and boundary behavior before any mechanism is allowed to evaluate the relation at scale.
How it implements the components¶
recurrence_relation— the equation is the relation expressing each subproblem's value in terms of smaller or neighboring ones.state_representation— it declares the state variable the relation ranges over and that decides subproblem equivalence.dependency_order— by fixing which subproblems depend on which, it sets the direction in which the dependencies must be resolved.
The equation states dependencies but does not carve out the subproblem_definition boundaries or specify the recombination_rule that reassembles a global solution — that surrounding procedure is its close relative the Dynamic Programming Method's — and it stores nothing, since the memoized_solution belongs to the Dynamic Programming Table.
Related¶
- Instantiates: Dynamic Subproblem Reuse — it is the formal relation that defines the reuse structure's dependencies.
- Sibling mechanisms: Dynamic Programming Method · Dynamic Programming Table · Memoization Cache · Modular Planning Template · Precedent Index · Reusable Playbook Library · Cache Invalidation Review
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Recurrence Equation operates by computes a subproblem value from specified neighboring or smaller subproblem values using a recurrence. That concrete deployed or enacted form is Analysis, Modeling & Optimization under the frozen taxonomy.
Nearest alternative: Representation, Specification & Plan — Although Representation, Specification & Plan can support this mechanism, the frozen evidence makes its operative form the act that computes a subproblem value from specified neighboring or smaller subproblem values using a recurrence; the alternative is therefore secondary rather than defining.
Review outcome: Adjudicated after independent review; high confidence.
Origin Attribution¶
Primary origin: Mathematics
Origin pattern: Convergent development
Present-day reach: Universal
Rationale: Recurrence relations originate in mathematics as definitions of sequences through prior terms.
Related originating lineages:
- Computer Science & Software Engineering — Algorithm analysis and dynamic programming materially made recurrence equations executable subproblem specifications.
Review resolution: Both blind reviewers agree that mathematics is the primary origin. Explicit reconciliation of origin mode disagreement, domain reach disagreement adopts reviewer_a's classification because recurrence relations originate in mathematics as definitions of sequences through prior terms. The resulting lineage records alternates=computer_science, origin_mode=convergent, and domain_reach=universal; these describe formative provenance separately from later applicability.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
The Recurrence Equation is the narrowest member of the computational family: where the Dynamic Programming Method is the full decompose-order-solve-recombine procedure, this mechanism is only the relation at its heart. That is exactly why the two are so easy to conflate and why the split matters — you can change the equation (a new objective, a new state) without touching the method that evaluates it, and vice versa.
[n1] The Bellman equation, from Richard Bellman's principle of optimality, is the canonical recurrence: the value of a state equals the best immediate return plus the value of the successor state. Its correctness hinges on the state being a sufficient statistic — capturing everything about the past that affects the future — which is why an inadequate state representation is the deepest way a recurrence can be wrong. ↩