4

从理论上（即，不实际执行）确定某个树遍历递归算法将在 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位与64位等...） .

我还缺少其他东西吗？

更新：

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

4

1 回答 1

0

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

于 2015-05-03T15:47:55.510 回答