递归方法的间歇性堆栈溢出问题

Question

我有一个简单的方法，是为了课堂作业而编写的，使用递归（必须使用递归）来计算分形图案中的三角形数量:

public static BigInteger triangleFract(int layer) {
    if(layer < 0) {
        throw new IllegalArgumentException("Input must be >= 0");
    } else if(layer == 0) {
        return new BigInteger("0");
    } else if (layer == 1) {
        return new BigInteger("1");
    } else {
        return triangleFract(layer - 1)
              .multiply(new BigInteger("3"))
              .add(new BigInteger("2"));
    }
}

我一直在尝试了解 int 层可以有多大，以便限制用户输入。经过一些测试，我发现在约 6700+ 处会出现堆栈溢出，这是可以接受的。

让我困扰的是，如果层数达到数千层，该方法通常可以运行，但仍可能随机遇到 StackOverflowError。

例如，我选择将层数限制为 4444，它似乎几乎总是能够处理，但偶尔仍会发生溢出。

为什么会这样？有没有什么办法可以解决这个问题？

- Gyst

---

我想问：为什么要使用BigInteger？你也可以使用原始的long。 - Juvanis

我多次运行了triangleFract(7000)，没有出现任何StackOverflowError。 - arshajii

@BlueBullet 这将很快超出 long 的容量（从 layer = 41 开始）。 - arshajii

我的一个朋友是Java性能工程师，他告诉我这与内联有关。我们最好等他懒洋洋地过来，解释一下他的意思。 - user381105

你正在使用哪个JVM进行测试？ - meriton

Answer 1

也许JVM已经确定（通过逃逸分析）BigInteger可以在栈上分配而不是堆上。取决于何时实现此优化，所需的堆栈大小会有所不同。

也就是说，还可能有许多其他原因，行为很可能取决于您使用的JVM。

- meriton

Answer 2

考虑转换为迭代版本。如果您正在开发递归算法，必须控制级别深度，否则不要使用递归。

- Roman C

---

+1。这里有一个使用迭代而不是递归（遍历树）的示例：here - npgall

递归和迭代之间总是存在一条界线，有时候递归是简化解决方案的代价，即二叉树。 - Roman C

Answer 3

允许递归到那个深度是一种设计上的不良迹象。

尝试使用这个迭代版本：

public static BigInteger triangleFract(int layer) {
    if (layer < 0) {
        throw new IllegalArgumentException("Input must be >= 0");
    }
    if (layer == 0) {
        return BigInteger.ZERO;
    }
    BigInteger result = BigInteger.ONE;
    BigInteger two = new BigInteger("2");
    BigInteger three = new BigInteger("3");
    for (int i = 1; i < layer; i++) {
        result = result.multiply(three).add(two);
    }
    return result;
}

注意事项：

• 使用BigInteger.ZERO和BigInteger.ONE代替为这些值创建新实例
• 删除冗余的else——在终止语句（例如return）之后，是没有else的。
• 重复使用new BigInteger("2")和new BigInteger("3")，而不是在每次迭代时创建新实例

- Bohemian

---

他提出了非常具体的问题：为什么会波动？而且，他强调必须使用递归。 - user381105

@Bohemian FYI result 的值将会是 2 * pow(3, layer-1) - 1。因此你可以直接返回 (new BigInteger("3")).pow(layer-1).multiply(new BigInteger("2")).subtract(BigInteger.ONE)，从而避免使用循环。 - arshajii

你的代码有错误：result.multiply(three).add(two); 会返回一个未被分配给任何变量的 BigInteger。 - Radu Murzea

@SoboLAN 你说得完全正确！BigInteger是不可变的！我犯了一个新手错误。我现在已经修复了代码。谢谢。 - Bohemian

Answer 4

对于那些无法重现这种波动的人，请找到从哪个方法开始layer值将可靠地抛出StackOverflowError。 这个值越接近真实阈值，就越好。 现在从循环内调用此方法（在我的机器上maxLayer = 11500）：

int i = 11500;
while (true) {
    System.out.println(i);
    triangleFract(i++);
}

这将会抛出StackOverflowError。现在你需要稍微减少一点这个值（大约5-10%应该就可以）：

int i = 10500;
while (true) {
    System.out.println(i);
    triangleFract(i++);
}

在我的电脑上，这段代码没有抛出任何错误，并成功跳过了11500。实际上，一直到16000，程序都能正常工作。

所以，无论是什么问题，它可能与JVM优化有关。我尝试使用-XX:+PrintCompilation运行一个程序。我观察了JIT在循环中的工作方式：

117   1       java.lang.String::hashCode (64 bytes)
183   2       java.lang.String::charAt (33 bytes)
189   3       sun.nio.cs.UTF_8$Decoder::decodeArrayLoop (553 bytes)
201   4       java.math.BigInteger::mulAdd (81 bytes)
205   5       java.math.BigInteger::multiplyToLen (219 bytes)
211   6       java.math.BigInteger::addOne (77 bytes)
215   7       java.math.BigInteger::squareToLen (172 bytes)
219   8       java.math.BigInteger::primitiveLeftShift (79 bytes)
224   9       java.math.BigInteger::montReduce (99 bytes)
244  10       sun.security.provider.SHA::implCompress (491 bytes)
280  11       sun.nio.cs.UTF_8$Encoder::encodeArrayLoop (490 bytes)
282  12       java.lang.String::equals (88 bytes) 11400
289  13       java.lang.String::indexOf (151 bytes)
293  14       java.io.UnixFileSystem::normalize (75 bytes)
298  15       java.lang.Object::<init> (1 bytes)
298  16       java.util.jar.Manifest$FastInputStream::readLine (167 bytes)
299  17       java.lang.CharacterDataLatin1::getProperties (11 bytes)
300  18       NormalState::triangleFract (74 bytes)
308  19       java.math.BigInteger::add (178 bytes)
336  20       java.lang.String::lastIndexOf (151 bytes)
337  21       java.lang.Number::<init> (5 bytes)
338  22       java.lang.Character::digit (6 bytes)
340  23       java.lang.Character::digit (168 bytes)
342  24       java.lang.CharacterDataLatin1::digit (85 bytes)
343  25       java.math.BigInteger::trustedStripLeadingZeroInts (37 bytes)
357  26       java.lang.String::substring (83 bytes)
360  27       java.lang.String::lastIndexOf (10 bytes)
360  28       java.lang.String::lastIndexOf (29 bytes)
361  29       java.math.BigInteger::<init> (24 bytes)
361  30       java.lang.Integer::parseInt (269 bytes)
361  31       java.math.BigInteger::<init> (8 bytes)
362  32       java.math.BigInteger::<init> (347 bytes)
404  33       java.math.BigInteger::multiply (72 bytes)
404  34       java.math.BigInteger::add (123 bytes)

可能是编译问题吗？ 让我们尝试延迟编译，以便尽可能晚地影响我们。我尝试使用-XX:CompileThreshold标志进行操作，并很快找到了一个值（-XX:CompileThreshold=1000000），这个值不会让我的循环跳过11500。

更新

最终我成功地复制了它，而没有任何编译阈值的调整。对我来说，看起来只有在我的IDE（IntelliJ IDEA）中运行程序时才会发生这种情况。因此，它可能与IDEA的启动器有关。我复制了它的命令行并在一个小脚本中使用：

for I in `seq 1 100`; do 
        java ... com.intellij.rt.execution.application.AppMain \
        Triangle 2>&1| grep Stack; done | wc -l

我发现通常会打印出一些小于100（95-98）的内容。这与我手动执行时所看到的一致。当我跳过启动器时：

for I in `seq 1 100`; do 
        java \
        Triangle 2>&1| grep Stack; done | wc -l

它总是打印出100。

- user381105

---

你好，你能够重现这个“波动”吗？我知道如何找到出错的层。我的问题是每次我用这个值运行它时，都会出现堆栈溢出，而每次我用max-1运行时，都会得到正确的结果。完全没有任何波动。 - ishi

Answer 5

实际上有一些你可以做的事情：增加最大堆栈大小。这可以在JVM启动时使用选项-Xss来完成，如下所示：

java -Xss40m MainClass

注意不要设置过高的值。如果必须超过60M-70M，则建议重新设计您的代码。

- Radu Murzea

Answer 6

我无法重现你的'波动'效果。这是非常确定性的代码，所以每次都应该得到相同的结果（包括堆栈溢出错误）。

你是如何测试的？每次尝试4444测试时都运行一个新的jvm吗？（还是只是在循环中调用triangleFrac(4444);？）

你的操作系统，java版本等等是什么？

我问这些是因为我不太喜欢这样的未解决问题---像这样的问题可能会在关键时刻出现。

哦...顺便说一下，就算是值得，你也应该使用BigInteger的ONE和ZERO常量（对于2和3也是如此）。这应该可以节省相当多的内存（是的，我知道，这不是你的问题）。

- ishi

---

操作系统：Windows 7（x64） Java版本：1.7.0_09我使用一个简单的Swing GUI进行测试，其中有一个按钮，按下该按钮会运行带有输入字段数字的方法。通过阅读其他评论，如果您使用接近机器溢出的数字运行它，则问题更加明显。我只需按几次按钮进行测试，如果发生错误，通常在2次按下按钮内发生。 - Gyst

所以，基本上，你吞下Throwable并愉快地在同一个jvm上继续运行代码，对吧？我也是这样做的，可以通过这种方式将层推得更高。问题是，当你忽略错误时，jvm会发生什么鬼东西...它处于一种奇怪的状态...可能甚至会自动增加堆栈大小（？？）。无论如何，对我来说，吞咽throwables解释了jvm的任何不可预测行为 :)。 - ishi