Java递归class变量值重置为0

Question

我正在尝试使用递归实现硬币找零问题。我编写了以下代码，但遇到了静态 class 变量的问题。 'answer' 是一个 class 变量，我试图在循环中向它添加 return 值。这在 while 循环中工作正常但在 while 循环结束后答案重置为 0;

    while (i * currentCoin <= sum) {
    System.out.println("inside while; answer is " + answer);
          answer = answer
            + findCombinations(
                    sum - i * currentCoin,
                    new ArrayList<Integer>(denominations.subList(1,
                            denominations.size())));
    i++;

}

下面是我写的全部代码。您可以复制并运行查看。

    import java.util.ArrayList;
    import java.util.Collections;

    public class CoinChangeHashMap {
static int answer = 0;

public static void main(String[] args) {

    int[] array = new int[] { 7, 3, 2 };
    ArrayList<Integer> input = new ArrayList<Integer>();
    getList(array, input);
    findCombinations(12, input);
    System.out.println(answer);
}

private static void getList(int[] array, ArrayList<Integer> input) {

    for (int i : array) {
        input.add(i);
    }

}

public static int findCombinations(int sum, ArrayList<Integer> denominations) {

    if (denominations.size() == 1) {
        if (sum % denominations.get(0) == 0) {
            return 1;
        }
        return 0;

    }
    int i = 0;
    int currentCoin = denominations.get(0);

    while (i * currentCoin <= sum) {
        System.out.println("inside while; answer is " + answer);

        answer = answer
                + findCombinations(
                        sum - i * currentCoin,
                        new ArrayList<Integer>(denominations.subList(1,
                                denominations.size())));
        i++;

    }
    return 0;
}}

**我得到的输出是0。但预期输出是4。调试时我得到的输出是**

inside while; answer is 0
inside while; answer is 0
inside while; answer is 1
inside while; answer is 1
inside while; answer is 2
inside while; answer is 2
inside while; answer is 0
inside while; answer is 0
inside while; answer is 0
0

感谢任何帮助。

Answer 1

问题与您奇怪的代码结构有关，您有时通过修改静态变量 answer，有时通过方法的 return 值来传达递归调用的结果。

如果您更仔细地分析问题，您会发现部分结果不是在退出循环时丢失，而是在方法 return 之后的某个时间丢失。因此，请仔细考虑更新答案的方式：

answer = answer + findCombinations( /* ... */ );

在递归的最顶层，answer 最初是 0。当 Java 计算上面的表达式时，它首先计算左操作数，然后计算右操作数，然后将它们相加。也就是说，它计算 answer，得到结果 0，在它执行递归调用之前。 answer 的值可能会在递归调用过程中更新，但这些更改来得太晚了。只有递归的最底层 return 的值不同于零，因此如果递归调用本身至少递归更深一层，那么它将 return 为零。在那种情况下，总和被计算为 0 + 0，并分配给 answer，破坏了方法执行的任何更新。

您可以通过交换求和中操作数的顺序来解决问题，但是完全摆脱静态变量会更好，也不会更难。在方法中使用局部变量来累积结果，并在所有情况下通过方法的 return 值将总数传回给调用者。

Java递归class变量值重置为0

Java recursion class variable value is reset to 0

java

static-variables

while-loop