Change recursive to iterative

change.js

/*
How many different ways can we make change of $ 1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to change any given amount of money?

This problem has a simple solution as a recursive procedure. 
Suppose we think of the types of coins available as arranged in some order. Then the following relation holds:

The number of ways to change amount a using n kinds of coins equals

the number of ways to change amount a using all but the first kind of coin, plus
the number of ways to change amount a - d using all n kinds of coins, where d is the denomination of the first kind of coin.
To see why this is true, observe that the ways to make change can be divided into two groups: those that do not use any of the first kind of coin, and those that do. Therefore, the total number of ways to make change for some amount is equal to the number of ways to make change for the amount without using any of the first kind of coin, plus the number of ways to make change assuming that we do use the first kind of coin. But the latter number is equal to the number of ways to make change for the amount that remains after using a coin of the first kind.

Thus, we can recursively reduce the problem of changing a given amount to the problem of changing smaller amounts using fewer kinds of coins. Consider this reduction rule carefully, and convince yourself that we can use it to describe an algorithm if we specify the following degenerate cases:33

If a is exactly 0, we should count that as 1 way to make change.
If a is less than 0, we should count that as 0 ways to make change.
If n is 0, we should count that as 0 ways to make change.
*/

// recursive
function change(amount, coins) {
  if (amount == 0) return 1;
  else
    if (coins.length == 0 || amount < 0) return 0;
    else
      return change(amount, coins.slice(1)) + change(amount - coins[0], coins);
}
console.log(change(100, [50, 25, 10, 5, 1]));


// CPS
function changeCPS(amount, coins, k) {
  if (amount == 0)
    k(1);
  else
    if (coins.length == 0 || amount < 0)
      k(0);
    else
      changeCPS(amount, coins.slice(1),
        (n1) => {
          changeCPS(amount - coins[0], coins,
            (n2) => k(n1 + n2)
          )
        });
}
//changeCPS(100, [50, 25, 10, 5, 1], console.log); // stack overflow

// iterative
function changeDef(amount, coins, k) {
  var n = 0;
  while (true) {
    if (amount > 0 && coins.length > 0) {
      k = { amount: amount, coins: coins, next: k };
      coins = coins.slice(1);
    }
    else {
      if (k != null) {
        amount = k.amount - k.coins[0];
        coins = k.coins;
        k = k.next;
        if (amount == 0)
          n = n + 1;
      }
      else {
        return n;
      }
    }
  }
}
console.log(changeDef(100, [50, 25, 10, 5, 1], null));