java - 递归 G(n) 函数错误

Question

我有一个计算 g(n) 的函数，其中 g(n)=f(n,n) 并且可以递归定义为

f(i, j) = 1 3个 (f(i − 1, j) + f(i − 1, j − 1) + f(i, j − 1)),

f(0, 0) = 0; f(i, 0) = 1, i > 0; f(0, j) = 1, j > 0.

static final Map<List<Double>, Double> CACHE = new HashMap<>();

private static double f(double i, double j) {
    if (i == 0.0 && j == 0.0) return 0.0;
    if (i == 0.0 || j == 0.0) return 1.0;
    List<Double> key = Arrays.asList(i, j);
    Double a = CACHE.get(key);
    if (a != null)
        return a;
    double result =  (1.0 / 3) * (f(i - 1, j) + f(i - 1, j - 1) + f(i, j - 1));

    CACHE.put(key, result);
    return result;
}

private static double g(double n) {

    return f(n, n);

}



}

我正在尝试计算 n=10^1,10^2,10^3,10^4,10^5,10^6 的值。前 3 个结果计算正常，但接下来程序崩溃:

Exception in thread "main" java.lang.StackOverflowError
at java.util.HashMap$TreeNode.getTreeNode(HashMap.java:1873)
at java.util.HashMap.getNode(HashMap.java:575)
at java.util.HashMap.get(HashMap.java:556)
at javaapplication7.Question3.f(Question3.java:72)

谁能找到解决这个问题的方法？另外，存储和运行时的复杂性是多少？

Answer 1

问题就像异常的名称一样:StackOverflowError .对于 n = 10000 的情况，所以我们需要调用函数 f 10000*10000次，所有的函数调用都保存在Stack内存中，导致栈溢出。

• 因此，一种选择是您可以增加 Java 堆栈大小。

• 或者，您可以考虑从递归方法更改为迭代方法。

观察:计算状态f(i, j) ，我们只需要知道状态 f(i - 1, j), f(i - 1, j - 1)和状态f(i, j - 1) , 它只需要两个数组，一个保存当前 i 的结果, 一个保存 i - 1 的结果.所以我们可以想出这样的迭代解决方案，它只需要 O(2*n) 空间:

int[] lastResult = new int[n + 1];

for(int i = 1; i < n; i++){
    int[] f = new int[n + 1];
    for(int j = 1; j <= n; j++){
        f[j] = lastResult[j] + lastResult[j - 1] + f[j - 1];
    }
    lastResult = f;
}