StackOverflowError 递归循环

如果递归调用太深，则会产生一个 StackOverflowError。Java 为其线程堆栈上的每个方法调用分配一个新帧。但是，每个线程堆栈的空间是有限的。堆栈上的帧太多会导致堆栈溢出（SO）。

例

public static void recursion(int depth) {
    if (depth > 0) {
        recursion(depth-1);
    }
}

使用大参数调用此方法（例如，recursion(50000) 可能会导致堆栈溢出。确切的值取决于线程堆栈大小，而线程堆栈大小又取决于线程构造，命令行参数（如 -Xss）或默认大小 JVM。

解决方法

通过将每个递归调用的数据存储在数据结构中，可以将递归转换为循环。此数据结构可以存储在堆上而不是存储在线程堆栈中。

通常，恢复方法调用状态所需的数据可以存储在堆栈中，而 while 循环可以用于模拟递归调用。可能需要的数据包括：

• 调用该方法的对象（仅限实例方法）
• 方法参数
• 局部变量
• 执行或方法中的当前位置

例

以下类允许递归打印到指定深度的树结构。

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(")");
        }
    }

}

例如

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();

打印

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

这可以转换为以下循环：

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();

注意： 这只是一般方法的一个例子。通常，你可以想出一种更好的方式来表示帧和/或存储帧数据。