Recursive Decomposition Check¶
Checklist — instantiates Inductive Validity Extension
Checks that repeatedly decomposed subproblems preserve the assumptions needed to recombine results or continue decomposition safely.
When a problem is solved by breaking it into smaller versions of itself, the danger is not in any single split but in what the splits silently assume. Recursive Decomposition Check is a standing checklist run at the moment of decomposition: it verifies that every subproblem still satisfies the preconditions the method relies on, and — crucially — that whatever is required to recombine the sub-results is still true after the descent. Its defining move is looking in both directions at once: down (does the subproblem remain a legitimate instance of the same problem?) and back up (will the recombination step's assumptions hold when the sub-results return?). It is not about running the recursion and watching; it is a pre-flight review of the decomposition's obligations before you trust the descent.
Example¶
A graphics engine renders a curved surface by recursively subdividing it into smaller quadrilateral patches until each patch is flat enough to draw as two triangles, then stitching the triangles back together into a seamless mesh. The recursion is elegant and the base case ("flat enough") is easy to check — which is exactly why the recombination assumption goes unexamined. Recursive Decomposition Check runs the checklist against the split. Item one: does each sub-patch remain a valid patch (four corners, consistent winding)? Yes. Item two — the recombination obligation: do adjacent sub-patches share identical edge vertices so the stitched mesh has no gaps?
Here the checklist bites. When one patch subdivides but its neighbor does not, the finer patch introduces a mid-edge vertex the coarser neighbor never created — a "T-junction" — and the recombination assumption (shared edges) quietly fails, producing hairline cracks in the final surface. The check catches this as an unmet obligation at the decomposition rule, not after a customer sees the cracks. The fix constrains subdivision so neighbors stay compatible, and the checklist records the depth beyond which the constraint can no longer be guaranteed — the boundary where decomposition stops being provably safe.
How it works¶
- Enumerate the decomposition's obligations up front. List what must be true of each subproblem for the method to apply, and what must be true across subproblems for recombination to be valid.
- Check the same-instance invariant. Confirm each subproblem is still a legitimate instance of the original problem — same structure, same preconditions — not a subtly different one the base case won't cover.
- Check the recombination assumption explicitly. This is the item most often skipped: verify that combining sub-results reconstructs a valid whole (no gaps, no double-counting, no lost context).
- Mark the safe depth. Record how deep the decomposition may go before an obligation can no longer be guaranteed, and treat that as the boundary of the check's assurance.
Tuning parameters¶
- Obligation-list depth — a terse two-item check versus an exhaustive precondition register. A fuller list catches more but is heavier to maintain and run at every split.
- Recombination scrutiny — how hard the cross-subproblem assumption is stressed. Light scrutiny is fast but is exactly where silent gaps hide; heavy scrutiny costs review time.
- Same-instance strictness — whether a subproblem must match the parent exactly or only up to a stated relaxation. Loose matching handles ragged real problems but risks admitting a subproblem the method does not actually cover.
- Boundary conservatism — how far short of the first unprovable case the safe-depth boundary is drawn. A conservative margin is safer but forecloses legitimate deeper decomposition.
When it helps, and when it misleads¶
Its strength is catching the failure that recursion makes easy to overlook: a decomposition that is locally fine at every split yet globally invalid because the recombination assumption erodes with depth. It is grounded in well-founded recursion[n1] — the discipline that each descent moves toward a base case along a well-ordered measure — and it extends that discipline from "does it terminate?" to "does what we assumed to recombine still hold?"
Its failure mode is that a checklist only checks the obligations someone thought to list; an unarticulated assumption — one nobody realized the recombination depended on — sails straight through a green checklist. It can also breed checklist theatre, ticked ritually without genuine scrutiny of the recombination item, which is precisely the one that matters. The guarding discipline is to derive the obligation list from what recombination actually consumes, and to revisit it whenever the decomposition rule or the recombination step changes.
How it implements the components¶
invariant_definition— names the preconditions and recombination assumptions that must remain true across every level of descent; the checklist is a list of these invariants.proof_obligation_register— the enumerated obligations are a register of what must be discharged at each decomposition and recombination, checked rather than proved.extension_boundary— records the depth beyond which an obligation can no longer be guaranteed, bounding where safe decomposition stops.
It reviews obligations statically rather than driving the process live — it does not run each recursive call and watch a property hold, which is Recursive Process Validation's domain, nor does it prove the step deductively. It disclaims step_transition_rule, monitoring_checkpoint, and propagation_rule, which the runtime and formal siblings own.
Related¶
- Instantiates: Inductive Validity Extension — realizes the "do the recombination assumptions survive repeated decomposition?" check as a pre-flight review.
- Sibling mechanisms: Recursive Process Validation · Induction Proof · Counterexample Search · Invariant Propagation Test · Property-Based Testing · Scalable Policy Rule Audit · Staged Rollout Validation · Training Progression Validation
Editorial Notes¶
Form Classification¶
Form family: Assessment, Review & Assurance
Rationale: Recursive Decomposition Check operates as a bounded evaluation of existing evidence or work that produces a finding or disposition because it checks that repeatedly decomposed subproblems preserve the assumptions needed to recombine results or continue decomposition safely.
Independent corroboration: The frozen evidence defines Recursive Decomposition Check as 'Checks that repeatedly decomposed subproblems preserve the assumptions needed to recombine results or continue decomposition safely', so its operative form is Assessment, Review & Assurance.
Nearest alternative: Interface, Display & Cue — Recursive Decomposition Check includes features of a user-facing prompt, display, template, or perceptual cue that shapes attention and action at the point of use, but its defining operation is a bounded evaluation of existing evidence or work that produces a finding or disposition.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Multi-domain
Rationale: Repeated problem decomposition with assumptions that must remain valid at recomposition is algorithmic and compositional-verification practice; mathematical induction provides the proof discipline.
Related originating lineages:
- Mathematics — Induction independently supplies proof that assumptions persist across repeated decomposition.
Review resolution: The blind reviewers disagreed on primary lineage. Light authoritative research resolves the defining form in favor of computer_science: Repeated problem decomposition with assumptions that must remain valid at recomposition is algorithmic and compositional-verification practice; mathematical induction provides the proof discipline. The rejected primary is retained only when it materially shaped the mechanism, and present-day breadth is recorded separately as domain_reach=multi_domain.
Review outcome: Researched adjudication after independent review; high confidence.
Sources consulted:
Notes¶
[n1] Well-founded recursion is recursion in which each call decreases along a well-ordered measure, guaranteeing the descent reaches a base case. Recursive Decomposition Check borrows the framing but shifts the question from termination to preservation of the assumptions needed to recombine. ↩