评估树遍历递归算法（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选项由线程分配的，那么将这个数字除以递归算法使用的每个堆栈帧的估计值是否正确？

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

我还漏了什么吗？

更新：

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

Answer 1

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