将递归函数中的数据保存到列表中

Question

我正在研究一个函数，它使用递归调用将给定的输入分解为面值。

在每个步骤中，它都会递归为两个变量：

1. 继续当前的硬币：将其添加到列表中并递归。
2. 切换到下一个硬币：递增硬币pos和递归。

除了在剩余=0时打印列表中捕获的面额组合之外，我还打算捕获该列表的值并从函数返回它。

这是代码：

    static final int[] DENOMINATIONS = {9,5,3};

    private static void change(int remaining, List<Integer> coins, int pos)

        if (remaining == 0) {

       // This correctly prints the desired output. 
       // I want to return that exact value from the function.
            System.out.println(coins); 

        } else {
            if (remaining >= DENOMINATIONS[pos]) {
                coins.add(DENOMINATIONS[pos]);
                another.addAll(coins);
                change(remaining - DENOMINATIONS[pos], coins, pos);
                coins.remove(coins.size() - 1);
            }
            if (pos + 1 < DENOMINATIONS.length) {
                change(remaining, coins, pos + 1);
            }
        }
    }


    public static List<Integer> denominations(int amount) {
        List<Integer> result = new ArrayList<Integer>();
        List<Integer> another = new ArrayList<Integer>();
        change(amount, result, another ,0);
        System.out.println(another.size());
        return another;
    }

    public static void main(String[] args) {
        List<Integer> list = denominations(13);
        System.out.println(list);
    }

输出：[5,5,3]

Answer 1

change应返回表示是否已找到答案的布尔值。

所以更改正文看起来像这样：

if (remaining == 0) {
  return true;
}
...
if (change(...)) return true;
...
return false;  // It's last line of body

Answer 2

您似乎假设java是通过引用传递的，这不是真的。Java方法是通过值传递的。

我已经更新了您的代码：

更改方法：

private static List<Integer> change(int remaining, List<Integer> coins, int pos) { // Updated method return type;

    if (pos < 0 || pos >= DENOMINATIONS.length) { // check if position is invalid
        return new ArrayList<>(); // return an empty list
    }

    if (remaining == DENOMINATIONS[pos]) { // check if remaining is equal to denominations[pos]
        coins.add(DENOMINATIONS[pos]); // add the denominations to the coins result
        return coins; // return the result
    } else if (remaining > DENOMINATIONS[pos]) { // check if remaining is greater than denominations[pos]
        coins.add(DENOMINATIONS[pos]);// add the possible denominations to the coins result
        remaining = remaining - DENOMINATIONS[pos]; // calculate the new remaining
        if (remaining >= DENOMINATIONS[pos]) { // check if remaining is greater than or equal to denominations[pos]
            return change(remaining, coins, pos); // stick to this position
        } else {
            return change(remaining, coins, pos + 1); // increment pos to go to the lower denominations
        }
    } else if (remaining < DENOMINATIONS[pos]) { // check if remaining is lesser than denominations[pos]
        if (coins.isEmpty()) { // if coins is empty then go to the next denomination
            return change(remaining, coins, pos + 1);
        } else {
            coins.remove(coins.size() - 1); // remove the previous denomination
            return change(remaining + DENOMINATIONS[pos - 1], coins, pos); // go back to the previous remaining and // try this DENOMINATIONS[pos]
        }
    }
    return coins;
}

面额法：

public static List<Integer> denominations(int amount) {
    return change(amount, new ArrayList<Integer>(), 0);
}

INPUT：13
OUTPUT：[5,5,3]

Answer 3

您将不得不添加返回硬币；在Change方法的和，但您可以保持它的方式。返回和更改数组是一种代码味道，因为方法既对对象进行操作（修改它），又返回结果。

要使其正常工作，您可以按如下方式定义您的面额方法：

public static List<Integer> denominations(int amount) {
   List<Integer> result = new ArrayList<Integer>();
   change(amount, result, 0);
   return result;
}

编辑：

列表是空的，因为它唯一更改的地方是这里：

coins.add(DENOMINATIONS[pos]);
change(remaining - DENOMINATIONS[pos], coins, pos);
coins.remove(coins.size() - 1);

添加和删除元素的位置。是你写的东西让它空空如也：）

编辑2：

我建议传递第二个对象，它是您想要返回的列表的副本，并且不会被修改。