计算 n = ~11000 + 带有记忆的斐波那契递归方法时的堆栈溢出

Question

我有一个程序用递归方法计算第 n 个斐波那契数，同时使用记忆。

我达到了 n = 11000 左右，并且遇到了 Whosebug 异常。有人可以帮我解决这个问题吗？

这是我的代码：

public class BigInt {

static BigInteger[] fval;

public static void main(String[] args) {
    int index;
    Scanner input = new Scanner(System.in);
    index = input.nextInt();
    fval = new BigInteger[index + 1];

    System.out.println(fib_rec(index));
}

public static BigInteger fib_rec(int index) {
    BigInteger result = BigInteger.ONE;
    if (index <= 2) {
        return result;
    } else {
        if (fval[index] != null) {
            result = fval[index];
        } else {
            result = fib_rec(index - 1).add(fib_rec(index - 2));
            fval[index] = result;
        }
        return result;
    }
}

Answer 1

您出现 Whosebug 的原因是您运行内存不足。增加可用内存，更具体地说，增加堆栈大小。只需添加 -Xss1024mb 或您喜欢的任何大小。

处理这种情况的最好方法是实际上有一个更好的算法，这样你就不需要消耗大量内存。

Answer 2

你的记忆不会改变递归的深度...在调用 fib_rec(n) 时，它调用 fib_rec(n-1) 调用 fib_rec(n-2) 等。如果你颠倒顺序调用（所以你做 fib_rec(index - 2).add(fib_rec(index - 1)) 这应该允许你将堆栈深度大致减少一半，因为你会以两个为单位向下工作到根，然后用堆栈从下往上填充间隙感谢您的记忆。

但是，如果不更戏剧性地重写算法，就无法避免堆栈深度问题。

Answer 3

必然

对于足够大的输入值，WhosebugError 本质上是不可修复的。对此的论据是双重的。首先，Java does not have tail call optimization. Second, with each recursive call, Java has to allocate some memory, e.g. for parameters. Even if your method has no parameters, Java needs a little bit of memory to store the address to jump to after the method call has ended. Thus, you eventually will exhaust your memory, no matter how large. You can prolong the inevitable by starting the JVM with more stack memory. The option (as well as some others) can be found here.

我们可以做得更好吗？

是的，我们可以。但不是用递归算法。我们需要把这个递归算法变成一个迭代算法。事实上，each recursion can be transformed in an iteration ans vice-versa。仅此一点仍然不够，因为您的算法具有线性内存复杂性。我们实际上只需要两个值来计算下一个斐波那契数。这导致以下方法（伪代码）：

int fibonacci(int nth)
    if nth is smaller than 0
        then halt and catch fire

    if nth is smaller than 2
        then return nth

    int last <- 1
    int secondToLast <- 0;

    for (int ith <- 2; ith less or equal to nth, increment ith)
        int tmp <- last + secondToLast
        secondToLast <- last
        last <- tmp
    end for

    return last;

上述算法具有线性时间复杂度（假设加法可以在常数时间内完成）和常数内存复杂度，从而解决了你的问题。

Answer 4

在使用记忆时避免递归。这是一个例子：

public class BigInt {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int index = input.nextInt();

        System.out.println(fib_rec(index));
    }

    public static BigInteger fib_rec(int index) {
        if (index <= 2) {
            return BigInteger.ONE;
        }

        BigInteger[] fval = new BigInteger[index + 1];
        fval[0] = BigInteger.ONE;
        fval[1] = BigInteger.ONE;

        for (int i = 2; i <= n; i++) {
            fval[i] = fval[i-1].add(fval[i-2]);
        } 

        return fval[n];
   }
}

}

计算 n = ~11000 + 带有记忆的斐波那契递归方法时的堆栈溢出

Stack Overflow when computing n = ~11000 + fibonacci recursive method with memoization

java

stack-overflow

recursion

memoization

fibonacci