Java Language Recursion StackOverflowError & recursion to loop
Example
If a recursive call goes "too deep", this results in a StackOverflowError. Java allocates a new frame for every method call on its thread's stack. However, the space of each thread's stack is limited. Too many frames on the stack leads to the Stack Overflow (SO).
Example
public static void recursion(int depth) {
if (depth > 0) {
recursion(depth-1);
}
}
Calling this method with large parameters (e.g. recursion(50000) probably will result in a stack overflow. The exact value depends on the thread stack size, which in turn depends on the thread construction, command-line parameters such as -Xss, or the default size for the JVM.
Workaround
A recursion can be converted to a loop by storing the data for each recursive call in a data structure. This data structure can be stored on the heap rather than on the thread stack.
In general the data required to restore the state of a method invocation can be stored in a stack and a while loop can be used to "simulate" the recursive calls. Data that may be required include:
- the object the method was called for (instance methods only)
- the method parameters
- local variables
- the current position in the execution or the method
Example
The following class allows recursive of a tree structure printing up to a specified depth.
public class Node {
public int data;
public Node left;
public Node right;
public Node(int data) {
this(data, null, null);
}
public Node(int data, Node left, Node right) {
this.data = data;
this.left = left;
this.right = right;
}
public void print(final int maxDepth) {
if (maxDepth <= 0) {
System.out.print("(...)");
} else {
System.out.print("(");
if (left != null) {
left.print(maxDepth-1);
}
System.out.print(data);
if (right != null) {
right.print(maxDepth-1);
}
System.out.print(")");
}
}
}
e.g.
Node n = new Node(10, new Node(20, new Node(50), new Node(1)), new Node(30, new Node(42), null));
n.print(2);
System.out.println();
Prints
(((...)20(...))10((...)30))
This could be converted to the following loop:
public class Frame {
public final Node node;
// 0: before printing anything
// 1: before printing data
// 2: before printing ")"
public int state = 0;
public final int maxDepth;
public Frame(Node node, int maxDepth) {
this.node = node;
this.maxDepth = maxDepth;
}
}
List<Frame> stack = new ArrayList<>();
stack.add(new Frame(n, 2)); // first frame = initial call
while (!stack.isEmpty()) {
// get topmost stack element
int index = stack.size() - 1;
Frame frame = stack.get(index); // get topmost frame
if (frame.maxDepth <= 0) {
// termial case (too deep)
System.out.print("(...)");
stack.remove(index); // drop frame
} else {
switch (frame.state) {
case 0:
frame.state++;
// do everything done before the first recursive call
System.out.print("(");
if (frame.node.left != null) {
// add new frame (recursive call to left and stop)
stack.add(new Frame(frame.node.left, frame.maxDepth - 1));
break;
}
case 1:
frame.state++;
// do everything done before the second recursive call
System.out.print(frame.node.data);
if (frame.node.right != null) {
// add new frame (recursive call to right and stop)
stack.add(new Frame(frame.node.right, frame.maxDepth - 1));
break;
}
case 2:
// do everything after the second recursive call & drop frame
System.out.print(")");
stack.remove(index);
}
}
}
System.out.println();
Note: This is just an example of the general approach. Often you can come up with a much better way to represent a frame and/or store the frame data.
