Recursive traversal

As explained in 100 Java Mistakes and How to Avoid Them

Recursive traversal is the process of visiting a hierarchical or graph-like structure by recursively processing related child elements.

Recursive traversal processes a node, then recursively visits each child. It works naturally for trees and directed acyclic graphs, but cycles can repeat the same state until stack space is exhausted. section 5.4.2

Figure 5.7 Finite recursion (left) and infinite recursion (right)

Contrast finite recursion with infinite recursion caused by revisiting equivalent program states. section 5.4.2

Avoid traversal failures by distinguishing valid structure assumptions from traversal defects:

• Track previously visited nodes when cycles are legal or possible. section 5.4.2
• Fix the earlier data-structure mistake when cycles should be impossible; do not obscure a valid traversal with unnecessary protection. section 5.4.2

Self-referential collections

A list containing itself can make list hashCode() recurse until StackOverflowError; toString() protects against a direct self-cycle, but nested cycles remain problematic. section 5.4.2

How 100 Java Mistakes and How to Avoid Them covers it

How deep it goes

Describes node processing, recursive child calls, repeated state, stack exhaustion, and cycle handling without implementation detail.

Examples

Uses self-referential lists and standard hashCode() and toString() behavior to demonstrate recursive cycle failures and protection.

What it assumes

Assumes familiarity with recursive methods and data structures while distinguishing trees, directed acyclic graphs, and cyclic structures.

What you can do after

Diagnose stack overflow by checking for cycles, repeated state, and incorrect recursive calls, then choose tracking or upstream correction.

How it connects

Connects recursive traversal with trees, directed acyclic graphs, cycles, infinite recursion, StackOverflowError, hashCode(), and toString().

liveBookmanning.com

Read 100 Java Mistakes and How to Avoid Them on liveBook Get the book at manning.com

Related concepts

• cycleuses · A cycle is a recurring sequence of connected elements or events that returns to an earlier point, forming a loop.
• traversalalternative to · Traversal is the systematic process of visiting elements or nodes in a data structure according to its links, ordering, or a specified rule.

This explainer was generated by Manning's knowledge graph from the text of 100 Java Mistakes and How to Avoid Them. The section links point to the parts of the book it draws on.