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;
    }

}