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
– RobG, Commented Sep 18, 2015 at 3: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
– brianpgerson, Commented Sep 18, 2015 at 4:20
The accepted answer is nice but it's also very inefficient. You may like to check this 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
– Redu, Commented Apr 28, 2019 at 9:58

Nina Scholz · Accepted Answer · 2017-09-12 07:50:49Z

3

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

edited Sep 12, 2017 at 7:50

answered Sep 18, 2015 at 14:43

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

brianpgerson Over a year ago

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.

Collectives™ on Stack Overflow

Implementing a recursive coin change function in Javascript

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related