Java 整数对象的递归方法 StackOverflowError

Question

我一直在尝试制作斐波那契数 returner（给定输入 n returns 斐波那契序列中索引位置 n 处的元素）。我试图使它既递归又具有低 space 复杂性（我没有实例化任何新变量）。我使用 Integer 对象作为值，虽然我知道它们的值溢出（它们 return 负值），但这实际上是有意的（出于教育目的）。该函数称为 smartestFib，因为它比我的其他函数具有更低的 space 复杂性。

当我为 130 或更高调用 smartestFib(n) 时出现问题。它在 129 或更低的情况下工作得很好（考虑到溢出），但它为 130 及以上的情况提供了例外。主要问题是我无法找出异常到底是什么：它显示了太多错误，以至于我看不到第一个，因此不知道到底是什么错误。因为我不知道错误的类型，所以我无法捕捉到它。

我的代码是：

private static int smartestFib(Integer goalNum)
{   
    if (goalNum < 2)
        return 1;
    else
        return smartestFib(goalNum-2, 0, 1,1);
}

private static int smartestFib(Integer goalNum, Integer currentNum, Integer lastValue, Integer beforeLastValue) 
{   
    if (goalNum == currentNum)
        return lastValue + beforeLastValue;
    else
    {
        return smartestFib(goalNum, currentNum + 1, lastValue+beforeLastValue,lastValue);
    }
}

我真的很感激能在这个问题上提供一些帮助，因为这个问题的随意性让我相信这是一些我不知道的技术问题，而且我不知道去哪里找。非常感谢。

编辑：显然它可能是 WhosebugError，非常感谢！但现在我想知道，我有其他功能，具有更高的 space 复杂性，但他们没有这个问题。如何？

private static int smarterFib(int goalNum)
{
    assert (goalNum >= 0): "The variable goalNum may not negative.";

    if (goalNum < 2)
        return 1;
    else
    {
        ArrayList<Integer> sequenceList = new ArrayList<Integer>(Arrays.asList(new Integer[] {1,1}));
        return smarterFib(goalNum-2, sequenceList);
    }
}

    private static int smarterFib(int goalNum, ArrayList<Integer> priorValues) 
{
    assert (goalNum >= 0): "The variable goalNum may not negative.";
    assert (priorValues != null): "The array priorValues has not been initialized.";

    if (goalNum <= priorValues.size()-2)
        return (priorValues.get(priorValues.size()-1) + priorValues.get(priorValues.size()-2));
    else
    {
        priorValues.add(priorValues.get(priorValues.size()-1) + priorValues.get(priorValues.size()-2));
        return smarterFib(goalNum, priorValues);
    }
}

我不明白为什么这个不会导致问题而我的新问题却会..

Answer 1

递归程序通过再次调用相同的方法并获得收益（即，通过调用该方法的线程创建更多 stackframes）并且在达到默认堆栈大小后，您将获得 Whosebugerror.

所以要解决这个问题，您需要通过传递 -Xss 作为 JVM 参数来增加堆栈大小，您可以查看 here.

I have other functions, with higher space complexity, and they are not having this problem. How?

所以第一个和第二个程序的区别解释如下：

不同之处在于一个使用装箱（当您使用 Integer 类型作为 goalNum 变量时）而另一个使用原始 int 并且当您使用装箱时它会导致性能问题和程序无法完成。

所以将您的 goalNum 变量从 Integer 类型更改为 int 然后它起作用了（我测试过）：

private static int smartestFib(int goalNum, int currentNum, 
     int lastValue, int beforeLastValue) {   
         System.out.println(goalNum);
         if (goalNum == currentNum)
             return lastValue + beforeLastValue;
         else {
            return smartestFib(goalNum, 
                   currentNum + 1, lastValue+beforeLastValue,lastValue);
        }
 }

因此，总而言之，始终避免不必要的 Boxing/Unboxing（从原始类型转换为包装类型，即 int 到 Integer），当您是运行广泛的计算（就像在你的递归中）。您可以查看 here 以了解有关拳击如何导致性能问题的更多信息。

Answer 2

堆栈溢出不是基于例程的 space 复杂性；这意味着您已经在调用堆栈的 space 上使用过。每个活动函数调用都会占用一些堆栈 space，跟踪传入和传回的值，并且经常进行上下文切换 space（寄存器值等）。

SmarterFib 传递一个整数（一个词）和一个数组（一个词，通过引用；总内存使用量为 N（goalnum ) 单词加上几个单词开销）。堆栈中总共有 2N 个单词。

SmartestFib 为每次调用传递四个整数，或堆栈上的 4N 个单词。

我通常不会期望它们具有完全不同的运行时间堆栈要求：如果 SmartestFib 在 N=130 时破坏堆栈，我希望 SmarterFib 在 N=260 之前把它炸掉（有一些固定的调用开销）。

Java 整数对象的递归方法 StackOverflowError

Java recursion method StackOverflowError with Integer object

java

recursion

runtime-error

fibonacci