Recursive Decomposition¶

Complex problems can be solved by defining solutions in terms of smaller instances of the same problem, trusting the process to eventually reach trivial base cases.

Tension Addressed¶

Optimality vs. Simplicity (recursive solutions are often elegantly simple)

Recognizable As¶

Tree traversals, file system operations, nested data structure processing, grammar parsing, mathematical induction in proofs

Canonical Sources¶

McCarthy, Recursive Functions of Symbolic Expressions (1960); Polya, How to Solve It (1945, general problem decomposition)

Transfers To¶

Organizational hierarchy, document structure, UI component trees, legal/contractual structures, linguistic parsing

Sub-concepts: - Base case identification: The trivial instance that terminates recursion - Trust the recursion: Assume subproblems solve correctly; focus on combination - Stack depth awareness: Recursion consumes stack space proportional to depth