Implementing a recursive coin change function in Javascript

Question

I'm totally blocked with a recursive problem. It's one that other people have asked about, but nobody seems to have asked about it in JS that I can see (sorry if I've missed something!) and reading other answers isn't helping.

In any case, I have a recursive program that returns the minimum number of coins necessary:

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 

But when I try to modify it into returning not just the number of coins, but also the coins used, I keep exceeding the max number of stack calls or just crashing the console in Chrome.

Answer should look like:

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

Here's my code:

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;
        }
    }
}

The idea is that it should always be returning an array with the coin count and coins array. I stepped through the function and it appears to be returning the right answers, but it doesn't stop running.

I have a feeling it rests in the loseIt/useIt definitions, but when I test something like

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

where x and y are arrays formatted like the ones I'm returning in my function, it seems to return the right format all the way through.

I'm self-teaching this stuff, so no lab or TA to help me out - hoping someone can explain what I'm doing incorrectly here!

Answer 1

The problem

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])];

vs working

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

As you see, the call of change() is done once for loseIt and useIt. In the version for array with the coin count, the function change() is called twice with the same parameter, but here you need the array elements of the return value of the function.

Solution:

Basically the same as in the count only version. One call of change() for loseIt and useIt. Later you can use the array for further processing.

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; }