将 HashMap 传递给递归方法不起作用？

Question

我声明 HashMap 用于记忆并将其传递给递归方法，但看起来 HashMap 并未真正存储数据并在每次递归调用时重置。下面是一个例子：

    public static int fib(int n) {
        Map<Integer, Integer> memo = new HashMap<>();
        return fib(n, memo);
    }

    private static int fib(int n, Map<Integer, Integer> memo) {
        if (n < 0) {
            throw new IllegalArgumentException(
                "Index was negative. No such thing as a negative index in a series.");

        // base cases
        } else if (n == 0 || n == 1) {
            return n;
        }

        // see if we've already calculated this
        if (memo.containsKey(n)) {
            System.out.printf("grabbing memo[%d]\n", n);
            return memo.get(n);
        }

        System.out.printf("computing fib(%d)\n", n);
        int result = fib(n - 1) + fib(n - 2);

        // memoize
        memo.put(n, result);

        return result;
    }

输出如下

computing fib(10)
computing fib(9)
computing fib(8)
computing fib(7)
computing fib(6)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(6)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(7)
computing fib(6)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(8)
computing fib(7)
computing fib(6)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(6)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)

但是如果我将 HashMap 作为静态变量并在 fib() 之外声明它，它工作正常，但这不是我想要做的。谁能帮帮我？

谢谢。

Answer 1

方法 fib(int, Map) 实际上从未被递归调用。您每次创建的地图都不会被使用。摆脱 fib(int) 并替换为对 fib(int, Map).

的调用

fib(n - 1, memo) + fib(n - 2, memo);

将 HashMap 传递给递归方法不起作用？

Passing HashMap to recursive method doesn't work?

java

recursion

hashmap

memoization