递归方法的间歇性 StackOverflowError

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，它似乎几乎总是能够处理这个问题，但每隔一段时间它似乎仍然会溢出。

为什么要这样做？ 我能做些什么吗？

Answer 1

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

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

Answer 2

考虑转向迭代版本。我认为，如果您开发递归算法，您必须控制级别深度或根本不使用递归。

Answer 3

实际上您可以做一些事情：增加最大堆栈大小。这是在 JVM 启动时使用选项

-Xss

完成的，如下所示：

java -Xss40m MainClass

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

Answer 4

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

你是如何测试的？ 您是否为 4444 测试的每次尝试运行一个新的 jvm？ （或者只是在循环中调用 triangleFrac(4444); ？）。

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

我问这个问题是因为我真的不喜欢像这样未解决的问题——这样的事情可能会在你受伤的地方（和时间）咬你；）。

哦...顺便说一句，无论如何，您应该使用 BigInteger 中的 1 和 0 常量（并为 2 和 3 创建您自己的常量。这应该为您节省相当多的内存（是的，我知道，这不是你的问题）。

Answer 5

允许递归到那个深度是一种设计味道。

尝试这个迭代版本：

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

  - 在终止语句之后is没有

  else

  （例如

  return

  ）
• 重新使用

  new BigInteger("2")

  和

  new BigInteger("3")

  ，而不是每次迭代都创建新实例

Answer 6

对于那些无法重现这种波动的人。找到从哪个方法能够可靠地抛出

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。