StackOverflowError & recursion to loop

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

Now to load this file as a properties you need to call the loadFromXML() instead of the load() that you would use with regular .properties files.

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 CustomNodeExample {
    public int nodeValue;
    public CustomNodeExample leftChild;
    public CustomNodeExample rightChild;
 
    public CustomNodeExample(int value) {
        this(value, null, null);
    }
 
    public CustomNodeExample(int value, CustomNodeExample left, CustomNodeExample right) {
        this.nodeValue = value;
        this.leftChild = left;
        this.rightChild = right;
    }
 
    public void printTree(final int maxDepth) {
        if (maxDepth <= 0) {
            System.out.print("(...)");
        } else {
            System.out.print("(");
            if (leftChild != null) {
                leftChild.printTree(maxDepth - 1);
            }
            System.out.print(nodeValue);
            if (rightChild != null) {
                rightChild.printTree(maxDepth - 1);
            }
            System.out.print(")");
        }
    }
 
    public static void main(String[] args) {
        // Example usage
        CustomNodeExample rootNode = new CustomNodeExample(10,
                new CustomNodeExample(20,
                        new CustomNodeExample(50),
                        new CustomNodeExample(1)),
                new CustomNodeExample(30,
                        new CustomNodeExample(42),
                        null));
 
        rootNode.printTree(2);
        System.out.println();
    }
}

Prints

((...)20(...))10((...)30)

This could be converted to the following loop:

public class TreeTraversalExample {
    public final TreeNode treeNode;
    public int traversalState = 0;
    public final int maxTraversalDepth;
 
    public TreeTraversalExample(TreeNode treeNode, int maxTraversalDepth) {
        this.treeNode = treeNode;
        this.maxTraversalDepth = maxTraversalDepth;
    }
}
 
List<TreeTraversalExample> traversalStack = new ArrayList<>();
traversalStack.add(new TreeTraversalExample(rootNode, 2)); // initial traversal frame
 
while (!traversalStack.isEmpty()) {
    int stackIndex = traversalStack.size() - 1;
    TreeTraversalExample currentFrame = traversalStack.get(stackIndex);
 
    if (currentFrame.maxTraversalDepth <= 0) {
        // Terminal case (too deep)
        System.out.print("(...)");
        traversalStack.remove(stackIndex); // drop frame
    } else {
        switch (currentFrame.traversalState) {
            case 0:
                currentFrame.traversalState++;
                System.out.print("(");
                if (currentFrame.treeNode.left != null) {
                    // Add new frame (recursive call to left and stop)
                    traversalStack.add(new TreeTraversalExample(currentFrame.treeNode.left, currentFrame.maxTraversalDepth - 1));
                    break;
                }
            case 1:
                currentFrame.traversalState++;
                System.out.print(currentFrame.treeNode.data);
                if (currentFrame.treeNode.right != null) {
                    // Add new frame (recursive call to right and stop)
                    traversalStack.add(new TreeTraversalExample(currentFrame.treeNode.right, currentFrame.maxTraversalDepth - 1));
                    break;
                }
            case 2:
                // Do everything after the second recursive call & drop frame
                System.out.print(")");
                traversalStack.remove(stackIndex);
        }
    }
}
 
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.

Basic Programs

Learn All in Tamil © Designed & Developed By Tutor Joes | Privacy Policy | Terms & Conditions