Walk through the structure of a Composite hierarchy — the participants, where the recursion lives, and how a container computes an aggregate result such as total size or overall validity.

## The three participants, precisely **Component** — the abstract type (interface or abstract base class). It declares exactly the operations clients want to invoke on *any* node. It is the only type appearing in client code and in the container's child collection. Nothing about children need appear here (see the transparency discussion), but the client operations must. **Leaf** — a node with no children. It implements each operation *terminally*: it computes and returns without calling the operation on anything else. In recursion terms, **Leaf is the base case**. A hierarchy usually has several leaf classes (File, Symlink, Button, Label) and they need not be related to each other beyond implementing Component. **Composite** — a node holding `children: Collection<Component>`. It implements each operation as: invoke the same operation on every child, then fold the results. **Composite is the recursive case.** It may also contribute its own intrinsic value (a directory's own metadata size, a panel's own border). **Client** — code holding `Component` references. It calls `root.size()` and receives a number, with no idea whether one node or a million were visited. ## Where recursion actually lives A point candidates often miss: **there is no recursive function anywhere.** No method calls itself by name. The recursion is *structural* — `Composite.size()` calls `Component.size()`, and because a child may itself be a Composite, control re-enters `Composite.size()` through **polymorphic dispatch** (the runtime selects the implementation from the object's actual class). This is why Composite is sometimes described as "recursion encoded in the type system rather than in a function." The practical consequence: to add a new node kind you write a new class; you never edit an existing traversal. ## The combining rule is per-operation A container is not a generic "loop and sum" machine. Each operation has its own fold: | Operation | Combining rule over children | Empty-container identity | Notes | |---|---|---|---| | `size()` | sum | `0` | May add the container's own overhead | | `price()` | sum, then maybe apply a bundle discount | `0` | Container can transform the aggregate | | `isValid()` | logical AND | `true` (vacuously valid) | Or `false` if your domain forbids empty groups | | `containsX()` | logical OR | `false` | Should short-circuit on the first hit | | `find(name)` | first non-absent result | absent | Order of children determines which match wins | | `depth()` | 1 + max | `1` (or `0`) | `max` has no identity — define explicitly | | `draw()` | side effect on each, in order | no-op | Order is semantically significant (z-order) | | `collectAll()` | concatenate | empty list | Flattening operation | **The empty-container case is where bugs live.** "Are all the items in this order in stock?" over an empty bundle returns `true` by the AND identity — which may be logically right and commercially wrong. Decide it deliberately and test it. Also decide whether the container's own intrinsic value participates: `Directory.size()` returning only the sum of children ignores directory metadata; whether that is correct is a domain question, not a pattern question. ## Termination conditions The recursion terminates only if two things hold: 1. **Leaves exist** on every path — a structure of nothing but containers would recurse until it ran out of children anyway, but a container that adds itself never terminates. 2. **The structure is acyclic.** Composite assumes a **tree**: exactly one root, each node reachable by exactly one path, no node is its own ancestor. If `add` lets you insert an ancestor, `size()` spins forever (or blows the stack). Therefore a robust `add` checks: the child is not this node, and this node is not reachable from the child. If you deliberately allow a node to have multiple parents, you have a **directed acyclic graph (DAG)**, not a tree. That is a valid and sometimes useful choice (shared subtrees save memory, as in a Flyweight-style scene graph), but it changes semantics: a summing aggregate now **double-counts** shared subtrees, a `parent` pointer is no longer well-defined, and traversals that must visit each node once need a **visited set**. ## Depth, stack, and cost Structural recursion consumes one stack frame per level. Trees built from user data (a deeply nested file system, a pathological JSON document, an expression parsed from untrusted input) can exceed the stack and crash the process — a real availability concern when the input is attacker-controlled. Mitigations: enforce a maximum depth on insert/parse, or replace the recursive walk with an explicit iterator that keeps a stack on the heap (this is essentially adding an Iterator to the Composite). Cost is invisible at the call site: `root.size()` looks like a field access. If children live behind lazy database or network loading, a single innocuous call can trigger one query per node — the **N+1 problem**. Fixes: eager/batched loading of the subtree, or caching the aggregate on the container and invalidating it up the parent chain when a descendant changes. ## Caching aggregates A common optimisation is memoising a container's aggregate (`cachedSize`). Correctness then requires that **any** mutation anywhere below invalidates every ancestor's cache — which requires parent pointers, which in turn requires `add`/`remove` to maintain them, and which is unsafe under concurrent mutation without synchronisation. This is why immutable trees are attractive: an immutable node's aggregate can be computed once at construction and never invalidated. ## Putting it together ``` interface Node { size(): int; valid(): bool } class FileNode implements Node { // base case bytes: int size() = bytes valid() = bytes >= 0 } class DirNode implements Node { // recursive case children: List<Node> size() = children.fold(0, (acc, c) -> acc + c.size()) // identity 0 valid() = children.all(c -> c.valid()) // identity true add(c: Node) { require(c !== this && !c.contains(this)) // cycle guard children.add(c) } } ``` That is the whole pattern: one interface, a terminal implementation, a delegating implementation, and a consciously chosen fold per operation.