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!

What values are valid for *amount*, and what values are in the *coins* array? — RobG, Sep 18 '15 at 03:38
I had a suspicion I'd forget something like that on my first SO question. I've edited the question above to include an example of the function call and expected results. @RobG — brianpgerson, Sep 18 '15 at 04:20
The accepted answer is nice but it's also very inefficient. You may like to check [this](https://stackoverflow.com/a/55383423/4543207) answer for a much more efficient algorithm along with their comparison. Even though it returns all possible coins, filtering the shortest one should be a trivial job either within the algorithm or after by a filter. — Redu, Apr 28 '19 at 09:58

Nina Scholz · Accepted Answer · 2017-09-12T07:50:49.813

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

Thank you! It seems relatively obvious now that the problem was the double call of `change()`, because at the time I didn't realize that calling loseIt doesn't require a return of any sort of coins — only useIt needs to do so, even if the loseIt call returns a useIt down the line. — brianpgerson, Sep 19 '15 at 00:20

Implementing a recursive coin change function in Javascript

1 Answers1