Need help with recursion

JavaScript
1

This is my code:

const curencyUnits = [
        ["PENNY", 0.01],
        ["NICKEL", 0.05],
        ["DIME", 0.1],
        ["QUARTER", 0.25],
        ["DOLLAR", 1],
        ["FIVE", 5],
        ["TEN", 10],
        ["TWENTY", 20],
        ["HUNDRED", 100]
    ];

const result = {};

function giveChange(change) {

    
    if (change <= 0) {
        return change;
    }
    for (let i = 8; i > 0; i--){
        let tmp = curencyUnits[i][1];
        if (change % tmp === change){
            continue;
        }
        if (change % tmp === 0) {
            console.log("if === 0");
            console.log(change % tmp);
            console.log(change);
            if (!(curencyUnits[i][0] in result)){
                result[curencyUnits[i][0]] = 0;
            }
            result[curencyUnits[i][0]] += 1;
            return change;
        }
        if (change % tmp <= tmp) {
            console.log("if <= tmp");
            console.log(change % tmp);
            console.log(change);
            if (!(curencyUnits[i][0] in result)){
                result[curencyUnits[i][0]] = 0;
            }
            result[curencyUnits[i][0]] += 1;
            giveChange(change - tmp)
        }

    }
}
giveChange(3.5);

The giveChange function is supposed to calculate the type and amount of currency units the change attribute has and include that in the result object which is outside the function.

After the giveChange function is called the result object becomes { DOLLAR: 3, QUARTER: 4 }. My question is: why am I getting 4 quarters instead of 2?

2

So something to consider: the recursion isn’t doing what you think. You call the function again, with a new change value, but i gets reset to 8 each time it’s called. I’m not surprised you’re getting an odd result from your change calculation - I’m more surprised you’re getting anything consistent as a response.

Edit: Sorry, that was less than informative, I was at that point tearing it down and rebuilding your recursive function to work. There are a few things going on, that make your solution less than ideal.

  • within your recursion, you are restarting the array index at 8 each time, thus not accessing other array members before calling the recursion.
  • Your logic is confusing (at least, to me). For example, rather than using change%tmp repeatedly, simply const howMany = change % tmp- that tells you how many of the current currency you should expect.
  • You may not be getting the results you expect from the modulo operator. That will return the remainder of the division (so 13 % 5 will always return 3). So your calculation in the line if (change % tmp <= tmp) should always return true.

If you’d like, I did rewrite and comment the CRAP out of a recursive giveChange(). Note that it isn’t the giveChange that is recursive, but a function defined inside there that does the actual recursion.

I was going post this a details thing, but this would be sort of a giveaway for the cash register project. Instead, I can give you some hints, and let you work your way through, or, if you like, I can share the repl where it’s working with you.

In the meantime, here’s a pseudocode version of what I did:

function giveChange(change){
  const makeChange =function(currencies, change, returnedObject){
    /***
     * create a variable to hold the last element of currencies, and remove that element
     * create a variable to hold the modulo value, dividing the change by that last element's number value
     * create a variable to store how many of that last currency you'd use - how would you calculate this one?
     *
     * if that howMany variable is greater than zero, let's add this currency and howMany value to our returnedObject
     *
     * if that modulo value, which will be our new change value, is equal to zero:
     *   return the returnedObject
     * otherwise, call our recursive function with:
     *   - the updated currencies array, 
     *   - the reduced change value (the modulo value thing),
     *   - the updated returnedObject.
     ***/
  }

  // Now, we simply need to call our recursive function! Call it with a COPY of
  //  our currencies array, with the change parameter, and an empty object.
}

huh. In the commented version on repl? It’s a LOT more lines than that. I really need to learn to shorten my darn comments…

1 Like
3

Wow! This is one very detailed reply. Didn’t expect it. Thank you for putting the time and effort.

You are probably right on this. The only thing I needed from this recursive function is run that for loop from the beginning (1 = 8) with a different value for the change attribute. Couldn’t think of a better way to do that.

I’m reading your comments but can’t figure out how to put that into code yet. I’ll keep trying for now.

4

You can’t recurse with a for loop, you need to think a little differently here. Recursion is more like a while loop, in that you keep running the recursive function until a predetermined condition is met.

Look at the parameters on my inner function. I specifically pass in everything, rather than rely on that global array. Why? Because, at each iteration, i pop the last ne, and i wanted the original untouched.

5

Ok, @ebv, what’s the logic behind choosing to go with recursive function?

In general, you want to use function in first place when you have lines of code to be used in multiple places, so you DRY. You have a function here, that is critically dependent on outside world and you’re going to use it just once… I would just stick with while (change) { ... } here