java - 计算 n = ~11000 + 带有内存的斐波那契递归方法时的堆栈溢出

Question

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

我在大约 n = 11000 时遇到了一个 stackoverflow 异常。有人可以帮我解决这个问题吗？

这是我的代码:

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

你的内存不会改变递归的深度...在调用 fib_rec(n) 时，它会调用 fib_rec(n-1) 调用 fib_rec(n-2) 等。如果您颠倒调用顺序(这样您就可以执行 fib_rec(index - 2).add(fib_rec(index - 1))应该允许您将堆栈深度大致减少一半，因为您将按两个向下工作到根，然后由于您的内存，从底部向上填充空白，堆栈深度为 1。

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