A stack overflow occurs when nested calls exhaust a thread’s call stack, producing StackOverflowError instead of a result. Recursion is often clear and useful, but each call consumes stack space. The depth that fails is not fixed: on JVM implementations it can vary with interpretation or JIT compilation, compilation tier, and the number of parameters and local variables. section 5.4
Two failures need different responses. Deep but finite recursion eventually reaches a base case, yet may exceed available stack space on large input. Infinite recursion repeats a call with the same relevant parameters and program state, returning to the original state while consuming another stack frame. section 5.4.1 section 5.4.2
/**
* @param s string to search in
* @param start start offset
* @param c symbol to search
* @return position of symbol c inside string s
* starting from start offset; -1 if not found
*/
static int indexOf(String s, int start, char c) {
if (start >= s.length()) return -1;
if (s.charAt(start) == c) return start;
return indexOf(s, start + 1, c);
}
A tail-recursive string search advances start toward the end of the string, but very long input can still overflow Java’s stack. section 5.4.1
static int indexOf(String s, int start, char c) {
while (true) {
if (start >= s.length()) return -1;
if (s.charAt(start) == c) return start;
start = start + 1;
}
}
Replacing the tail call with iteration removes recursive stack growth and permits arbitrarily long strings. section 5.4.1
Avoid stack overflow by choosing the remedy that matches the cause:
- Rewrite tail recursion as a loop when the maximum depth might exceed several hundred calls; IntelliJ IDEA can apply Replace Tail Recursion With Iteration. section 5.4.1
- Use Kotlin’s tailrec modifier only where applicable; it directs the compiler to turn valid tail recursion into a loop, unlike Java’s compiler. section 5.4.1
- For traversal of structures that may legally contain cycles, record visited nodes before revisiting them. section 5.4.2
- When cycles should be impossible, find and repair the earlier defect that created the cycle rather than complicating a valid recursive traversal. section 5.4.2
Self-referential collections
A list containing itself causes hashCode() to recurse until StackOverflowError; that behavior follows the specification. toString() handles a direct self-reference, but a longer collection cycle can still overflow. Avoid adding a collection to itself. section 5.4.2
Figure 5.7 Finite recursion (left) and infinite recursion (right)
The figure contrasts a recursive process that reaches an endpoint with one that keeps returning to prior state and grows without bound. section 5.4.2
