A tree organizes elements into parent-child relationships and ordinarily contains no cycles. Recursive traversal processes a node, then recursively visits each child; it is safe when cycles are impossible. section 5.4.2
Treat cycles according to their cause:
- Track previously visited nodes when cycles are legal or may be present, preventing repeated visits and stack overflow. section 5.4.2
- Fix the earlier construction mistake when a cycle violates the structure’s invariant; changing correct recursive traversal is unnecessary. section 5.4.2
Recursive traversal failure
A traversal that revisits a cyclic path can call itself with the same effective state indefinitely, eventually exhausting the call stack. The same pattern appears when a collection directly or indirectly contains itself. section 5.4.2
Figure 5.7 Finite recursion (left) and infinite recursion (right)
Compare finite recursion with infinite recursion to see how an unchanged state prevents termination. section 5.4.2
