什么时候可以增加 jvm (-Xss) 的最大堆栈大小？

Question

我在做什么 ？

我正在 coursera 上开设一门课程，该课程要求我编写一个计算树高的程序。输入是一个父数组，其中每个索引都是节点，其值是节点的父节点。如果节点是根节点，它的值将为 -1。

到目前为止我做了什么？

我编写了一个算法，通过递归遍历其子节点直到其根节点并将中间子节点的高度保存在数组（深度变量）中来检查树的高度。

为了摆脱这个异常，我尝试为我的递归调用找到最佳值，结果它接近3100k。此外，当我看到针对一些预定义测试用例测试我的算法的代码也已将1 << 26 的堆栈大小传递到线程构造函数中。

我需要知道什么？

1. 有没有更好的方法来解决这个问题？

2. 像这样增加堆栈大小可以吗？

这是代码

int computeHeight() {

    int[] depth = new int[n];

    int maxHeight = 0;

    for (int i = 0; i < n; i++) {

        int height = computeHeight(parent, depth, i);

        maxHeight = Math.max(height, maxHeight);

    }

    return maxHeight;

}

private int computeHeight(int[] parent, int[] depth, int idx) {

    if (parent[idx] == -1) {

        // root found

        depth[idx] = 1;

        return depth[idx];

    }

    // depth of parent unknown

    if (depth[parent[idx]] == 0) {

        computeHeight(parent, depth, parent[idx]);

    }

    depth[idx] = depth[parent[idx]] + 1;

    return depth[idx];

}

Answer 1

如果树向右或向左倾斜，例如如果每个节点只有一个右子节点，那么递归很容易导致计算器溢出（再次取决于堆栈设置），不确定输入之一是否具有您的情况。这可以以迭代方式完成：a) 将所有父项（数组中的值）添加到 HashSetb) 然后遍历所有节点（这里只是从 0 到 n 的索引），看看它是否存在于集合中，如果不存在，它就是一片叶子。c) 然后从叶子遍历到根来获取高度，同时将每个节点的高度存储在数组中，这样下次您就不必再次爬上相同的路径。d) 每次更新最大高度。

Answer 2

在现实生活中，只有当你知道深度被限制在一个很小的值时，你才应该使用递归。例如，递归地测量一棵平衡树很好，但递归地测量一棵不平衡树就不行了。

Answer 3

您遇到堆栈溢出错误似乎很奇怪，我假设这是一个如此简单的问题；当它是一棵非常大的树或者您出于某种原因在它期间加载大量 RAM 时，这只会成为递归的问题。我建议你发布你的代码。至于增加堆栈大小，这不是问题，因为您只是在做练习题。然而，在现实世界中，这可能会带来挑战，并且是使用递归的风险之一。如果您在各种设备上使用您的应用程序，由于设备的限制，增加堆栈大小可能并不总是可行的。相反，我建议您尽可能避免使用递归，除非您知道要递归的树足够小而不会导致溢出。