从理论上(即不实际执行)确定某种树遍历递归算法将在 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选项 http://docs.oracle.com/cd/E13150_01/jrockit_jvm/jrockit/jrdocs/refman/optionX.html#wp1024112,将这个数字除以我的递归算法使用的每个堆栈帧的估计是否正确?
通过将参数和局部变量的大小添加到程序计数器的大小来估计每个堆栈帧的大小是否正确,其中程序计数器的大小取决于体系结构(32 位与 64 位等......) 。
我还缺少其他东西吗?
UPDATE:
我确实知道递归算法可以转换为迭代算法以避免堆栈溢出错误。这只是一个关于递归算法的理论问题。
我知道这主要是理论问题,但它是有效的问题。你的估计是正确的。除了堆栈转到 Xms,但局部变量转到 Xmx。因此,根据实际数据,您在每次迭代中使用的内容以及树的可用 RAM 深度的实际大小确实有所不同。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)