Recursion solves a problem through smaller subproblems by having a method or algorithm invoke itself. It can produce cleaner algorithms than loops, but each call consumes thread-stack space. section 5.4
Tail recursion and stack depth
A tail-recursive sum carries its partial result in an accumulator and decreases the limit on each call. Large inputs can still cause StackOverflowError in Java. Kotlin's tailrec modifier can compile this pattern into a loop; Scala can optimize eligible tail calls. section 5.4.1
Use recursion deliberately:
- Avoid arbitrarily deep recursion because maximum stack depth varies with compilation mode, parameters, local variables, and the virtual machine. section 5.4
- Rewrite tail recursion as a loop when stack growth is unacceptable; IntelliJ IDEA provides a Replace Tail Recursion With Iteration action. section 5.4.1
- Replace non-tail recursion with heap-based structures such as ArrayDeque, and track visited elements when traversing data that may contain cycles. section 5.5
Recursive tree search
A Node.find method checks the current node, recursively searches each child, and returns null when no match exists. The same traversal can use an ArrayDeque instead, avoiding recursive stack growth.
