A heap is the runtime memory area used for dynamically allocated objects and data structures. In recursive algorithms, moving intermediate call state into a heap-resident collection can replace a stack-depth limit with a heap-size limit. section 5.4.1
Use heap-backed state when recursion may become unusually deep:
- Rewrite tail recursion as a loop when possible; this avoids accumulating recursive stack frames. section 5.4.1
- For non-tail recursion, store pending nodes or call state in an ArrayDeque or another side collection. section 5.4.1
- Expect the iterative version to be longer, and preserve every variable needed between recursive calls. section 5.4.1
Iterative tree traversal
A recursive tree search can overflow on very deep trees. An iterative search keeps nodes to visit in a Deque, allowing traversal depth to be limited by heap capacity rather than stack capacity. section 5.4.1
Node find(String name) {
Deque<Node> stack = new ArrayDeque<>();
stack.add(this);
while (!stack.isEmpty()) {
Node node = stack.pollLast();
if (node.name().equals(name)) return node;
Collections.addAll(stack, node.children());
}
return null;
}
Shows a Java tree search that replaces recursive calls with an ArrayDeque-backed traversal stack. section 5.4.1
