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

注意： 這只是一般方法的一個例子。通常，你可以想出一種更好的方式來表示幀和/或儲存幀資料。