java - 评估树遍历递归算法中是否可能出现堆栈溢出错误(Java)

Question

从理论上(即不实际执行)确定某种树遍历递归算法在 Java 中会产生堆栈溢出的情况的最佳方法是什么？

为了澄清我的问题，请考虑以下示例。给定一个用 Java 实现的简单二叉树:

public class Node {
    private int value;
    private Node left;
    private Node right;
    ...

    //in-order traversal
    public void inOrder() {
        if (left != null) {
            left.inOrder();
        }
        System.out.println(value);
        if (right != null) {
            right.inOrder();
        }
    }
}

在该算法中，嵌套递归调用的最大数量与树的深度成线性关系。那么我如何估计允许中序遍历算法(或类似算法)在不引发堆栈溢出错误的情况下完成的树的最大深度？

如果最大堆栈大小由线程通过 -Xss option 分配，将这个数字除以我的递归算法使用的每个堆栈帧的估计是否正确？

通过将参数和局部变量的大小添加到程序计数器的大小来估计每个堆栈帧的大小是否正确，其中程序计数器的大小取决于体系结构(32 位与 64 位等。 ..).

我还漏掉了什么吗？

更新:

我知道可以将递归算法转换为迭代算法以避免堆栈溢出错误。这只是一个关于递归算法的理论问题。

Answer 1

我知道这主要是理论问题，但它是有效的问题。你的估计是对的。除了堆栈转到 Xms 但局部变量转到 Xmx。因此，基于真实数据，您在每次迭代中使用的内容和树的可用 RAM 深度的实际大小确实会有所不同。