javascript - 在 Javascript 中实现递归硬币找零功能

Question

我完全被一个递归问题困住了。这是其他人问过的问题，但似乎没有人在我能看到的 JS 中问过它(抱歉，如果我错过了什么!)，阅读其他答案也无济于事。

无论如何，我有一个递归程序可以返回所需的最少硬币数:

function change(amount, coins){
    if (amount == 0){
        return 0;
    } else if (coins.length == 0 && amount > 0){
        return Infinity;
    } else if (coins[0] > amount){
        return change(amount, coins.slice(1));
    } else {
        var loseIt = 0 + change(amount, coins.slice(1));
        var useIt = 1 + change(amount - coins[0], coins);
        return Math.min(loseIt, useIt);
    }
}

change(48, [1, 5, 10, 25, 50])
>>> 6
change(48, [1, 7, 24, 42])
>>> 2 

但是，当我尝试将其修改为不仅返回硬币数量，还返回使用的硬币时，我不断超出堆栈调用的最大数量，或者只是让 Chrome 中的控制台崩溃。

答案应该是这样的:

change(48, [1, 5, 10, 25, 50])
>>> [6, [25, 10, 10, 1, 1, 1]]
change(48, [1, 7, 24, 42])
>>> [2, [24, 24]] 

这是我的代码:

function change(amount, coins){
    if (amount == 0){
        return [0,[]];
    } else if (coins.length == 0 && amount > 0){
        return [Infinity,[]];
    } else if (coins[0] > amount){
        return change(amount, coins.slice(1));
    } else {
        var loseIt = [change(amount, coins.slice(1))[0], [].concat(change(amount, coins.slice(1))[1])];
        var useIt = [1 + change(amount - coins[0], coins)[0], [coins[0]].concat(change(amount - coins[0], coins)[1])];
        if (useIt[0] > loseIt[0]){
            return loseIt;
        } else {
            return useIt;
        }
    }
}

想法是它应该总是返回一个包含硬币计数和硬币数组的数组。我单步执行了该函数，它似乎返回了正确的答案，但它并没有停止运行。

我觉得它存在于 loseIt/useIt 定义中，但是当我测试类似

的内容时

[x[0] + y[0], x[1].concat(y[1])]

其中 x 和 y 是格式与我在我的函数中返回的数组一样的数组，它似乎一直返回正确的格式。

我正在自学这些东西，所以没有实验室或助教来帮助我 - 希望有人能解释我在这里做错了什么!

Answer 1

问题

var loseIt = [
    change(amount, coins.slice(1))[0], [].concat(
    change(amount, coins.slice(1))[1])];
var useIt = [1 + 
    change(amount - coins[0], coins)[0], [coins[0]].concat(
    change(amount - coins[0], coins)[1])];

与工作

var loseIt = 0 + change(amount, coins.slice(1));
var useIt = 1 + change(amount - coins[0], coins);

如您所见，change() 的调用只针对loseIt 和useIt 完成一次。在带有硬币计数的数组版本中，函数 change() 使用相同的参数被调用了两次，但是这里您需要函数返回值的数组元素。

解决方法:

基本上与仅计数版本相同。为 loseIt 和 useIt 调用一次 change()。稍后您可以使用该数组进行进一步处理。

function change(amount, coins) {
    if (amount === 0) {
        return [0, []];
    }
    if (coins.length === 0 && amount > 0) {
        return [Infinity, []];
    }
    if (coins[0] > amount) {
        return change(amount, coins.slice(1));
    } else {
        var loseIt = change(amount, coins.slice(1));  // just one call of change
        var useIt = change(amount - coins[0], coins); // just one call of change
        if (loseIt[0] < 1 + useIt[0]) {
            return loseIt;
        } else {
            return [1 + useIt[0], useIt[1].concat(coins[0])];
        }
    }
}

console.log(change(12, [9, 6, 1]));                   // [2, [6, 6]]
console.log(change(48, [1, 5, 10, 25, 50]));          // [6, [25, 10, 10, 1, 1, 1]]
console.log(change(48, [1, 7, 24, 42]));              // [2, [24, 24]]
console.log(change(189, [1, 77, 17, 63, 92, 8, 14])); // [3, [63, 63, 63]]

.as-console-wrapper { max-height: 100% !important; top: 0; }