2

在 n=1000 之前堆栈溢出。是因为对 long[] 参数的引用，JVM 觉得需要保留每个堆栈帧（疯狂猜测），还是我做错了什么？

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        fibonacciMemoized(1000);
        long end = System.currentTimeMillis();
        System.out.println("\nTotal run time: " + (end-start));
    }

    public static void fibonacciMemoized(int n) {
        long[] fibMemos = new long[n+1];
        for (int i = 0;  i < fibMemos.length; i++) {
            fibMemos[i] = Long.MAX_VALUE;
        }
        long fibResult = fib(n, 1, 0, fibMemos);
        System.out.println(fibResult);
    }

    public static long fib(int n, long fibAcc, long fibPrev, long[] fibMemos) {
        if (fibMemos[n] != Long.MAX_VALUE){
            return fibMemos[n];
        } else if (n == 0) {
            return fibPrev;
        } else if (n == 1){
            return fibAcc;
        } else {
            long result = fib(n-1, fibAcc+fibPrev, fibAcc, fibMemos);
            fibMemos[n] = result;
            return result;
        }
    }
4

3 回答 3

4

我想这更像是一个答案而不是评论：

为什么我仍然使用尾递归斐波那契算法烧毁堆栈？

因为Java不支持尾调用消除。

于 2013-03-21T03:21:31.410 回答
1

记忆化的关键问题是记忆化函数的后续调用将使用相同参数的预计算值。

在您的代码中，您之前没有调用过该函数，因此没有以前的结果可以重用，并且您开始以 1000 的值调用它，这会在fib()with 的末尾进行递归调用fib(n-1, fibAcc+fibPrev, fibAcc, fibMemos)，因此您正在炸毁堆栈有 1000 个递归调用。

于 2013-03-21T03:31:27.327 回答
0

尝试使用增加堆栈的选项来运行它，例如 java -Xss4m 或更多。

注意：使用 -Xss 设置每个线程的堆栈大小，这是一个非常糟糕的主意。

于 2013-03-21T03:27:13.720 回答