CODEWITHSUNDEEP
javascript
y2knoproblem
y2knoproblem

Reputation: 570

Javascript Recursive Call Producing Ghost Outcomes

I'm creating an function called changeCounter. It accepts a whole number and returns an array, changeDue, with the correct change in bills ordered from highest to lowest. Example:

    changeCounter(13)
    changeDue = [["TEN", 10], ["ONE", 1], ["ONE", 1], ["ONE", 1]]

The recursive function I created works as expected for numbers up to 5. Numbers greater than 5 returns extra bills. In other words it won't stop when due = 0. I've tried many variations. I would appreciate feedback as to what the problem is.

var changeDue = [];
var bills = [["ONE HUNDRED", 100],["TWENTY", 20],["TEN", 10],["FIVE", 5],["ONE", 1]];

function changeCounter(due) {
  for(var i = 0; i < bills.length; i++) {
    if(due >= bills[i][1] && due > 0) { // Should stop recursive loop here when due = 0!
      changeDue.push(bills[i]);
      console.log(due - bills[i][1]); // debug
      changeCounter(due - bills[i][1]);
    }
  }
  return changeDue;
}


console.log(changeCounter(8));

This outputs:

> [["FIVE", 5], ["ONE", 1], ["ONE", 1], ["ONE", 1], ["ONE", 1], ["ONE",
> 1], ["FIVE", 5]...]

Returns an array with 17 elements. Should only return first 4 elements.

Upvotes: 0

Views: 53

Answers (3)

Shilly
Shilly

Reputation: 8589

You're calling the recursing inside the for loop, find a better place to put it in or just use a while loop.

function changeCounter(due) {
    var due = due,
        nextBill;
    while (due > 0) {
        nextBill = bills.reduce(function (acc, bill) {
            if (!acc && due >= bill[1]) acc = bill;
            return acc;
        }, false);
        due = due - nextBill[1];
        changeDue.push(nextBill);
    }
}

Upvotes: 1

user5192753
user5192753

Reputation:

You don't really need a recursive function:

function changeCounter(amount) {
    var result = [];

    for (var i = 0, billsCount = bills.length; i < billsCount; i++) {
        if (amount == 0) {
            break;
        }

        var numberOfBills = Math.floor(amount / bills[i][1]);
        if (numberOfBills > 0) {
            amount -= numberOfBills * bills[i][1];
            for (var j = 0; j < numberOfBills; j++) {
                result.push(bills[i]);
            }
        }
    }

    return result;
}

Upvotes: 0

Paul Roub
Paul Roub

Reputation: 36438

When you call changeCounter() recursively within itself, the value of due within the calling function doesn't change. So when due is 8, and you log a $5 bill, then call:

changeCounter(due - bills[i][1]);

to process the remaining $3, that's fine. But then that call returns to a world where due == 8, and your outer loop continues, throwing another $1 bill on the pile. Similar things happen in the due == 3 version, and so on.

A break; will do the job, once you've made your recursive call:

var changeDue = [];
var bills = [
  ["ONE HUNDRED", 100],
  ["TWENTY", 20],
  ["TEN", 10],
  ["FIVE", 5],
  ["ONE", 1]
];

function changeCounter(due) {
  for (var i = 0; i < bills.length; i++) {
    if (due >= bills[i][1]) {
      changeDue.push(bills[i]);
      changeCounter(due - bills[i][1]);
      break;
    }
  }
  return changeDue;
}


console.log(changeCounter(8));

Upvotes: 0

Related Questions