递归方法的间歇堆栈溢出

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

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