英文:
Passing HashMap to recursive method doesn't work?
问题
我使用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.");
} else if (n == 0 || n == 1) {
return n;
}
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, memo) + fib(n - 2, memo);
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)
grabbing memo[2]
grabbing memo[3]
grabbing memo[4]
grabbing memo[5]
grabbing memo[6]
grabbing memo[7]
grabbing memo[8]
grabbing memo[9]
computing fib(2)
grabbing memo[3]
grabbing memo[4]
grabbing memo[5]
grabbing memo[6]
grabbing memo[7]
grabbing memo[8]
computing fib(3)
grabbing memo[4]
grabbing memo[5]
grabbing memo[6]
grabbing memo[7]
grabbing memo[8]
computing fib(2)
grabbing memo[3]
grabbing memo[4]
grabbing memo[5]
grabbing memo[6]
grabbing memo[7]
computing fib(4)
grabbing memo[5]
grabbing memo[6]
grabbing memo[7]
grabbing memo[8]
computing fib(3)
grabbing memo[4]
grabbing memo[5]
grabbing memo[6]
grabbing memo[7]
computing fib(2)
grabbing memo[3]
grabbing memo[4]
grabbing memo[5]
grabbing memo[6]
computing fib(5)
grabbing memo[6]
grabbing memo[7]
grabbing memo[8]
computing fib(3)
grabbing memo[4]
grabbing memo[5]
grabbing memo[6]
computing fib(2)
grabbing memo[3]
grabbing memo[4]
grabbing memo[5]
computing fib(4)
grabbing memo[5]
grabbing memo[6]
grabbing memo[7]
computing fib(3)
grabbing memo[4]
grabbing memo[5]
computing fib(2)
grabbing memo[3]
grabbing memo[4]
computing fib(6)
grabbing memo[5]
grabbing memo[6]
computing fib(3)
grabbing memo[4]
grabbing memo[5]
computing fib(2)
grabbing memo[3]
computing fib(7)
grabbing memo[4]
grabbing memo[5]
computing fib(2)
grabbing memo[3]
grabbing memo[4]
computing fib(5)
grabbing memo[5]
grabbing memo[6]
computing fib(3)
grabbing memo[4]
grabbing memo[5]
computing fib(2)
grabbing memo[3]
grabbing memo[4]
computing fib(4)
grabbing memo[5]
grabbing memo[6]
computing fib(3)
grabbing memo[4]
grabbing memo[5]
computing fib(2)
grabbing memo[3]
grabbing memo[4]
computing fib(8)
grabbing memo[5]
grabbing memo[6]
computing fib(3)
grabbing memo[4]
grabbing memo[5]
computing fib(2)
grabbing memo[3]
grabbing memo[4]
computing fib(5)
grabbing memo[5]
grabbing memo[6]
computing fib(3)
grabbing memo[4]
grabbing memo[5]
computing fib(2)
grabbing memo[3]
grabbing memo[4]
computing fib(6)
grabbing memo[5]
grabbing memo[6]
computing fib(3)
grabbing memo[4]
grabbing memo[5]
computing fib(2)
grabbing memo[3]
grabbing memo[4]
但是如果我将HashMap声明为静态变量并将其放在fib()之外，它就能正常工作，但这不是我想要的。有人能帮我解决吗？
谢谢。
英文:
I declare HashMap for memoization and pass it into recursive method but it looks like HashMap doesn't really store data and getting reset each recursive call. Here is an example below:
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;
}
output is like below
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)
But it's working fine if I have HashMap as static variable and declare it out side of my fib() but that's not what I wanted to do. Can anyone help me out?
Thanks.
答案1
得分: 1
方法fib(int, Map)实际上从未被递归调用。每次创建的映射都没有被使用。移除fib(int)，并替换为调用fib(int, Map)。
fib(n - 1, memo) + fib(n - 2, memo);
英文:
The method fib(int, Map) never actually gets called recursively. The map you create each time is never used. Get rid of fib(int) and replace with calls to fib(int, Map).
fib(n - 1, memo) + fib(n - 2, memo);
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论