Designing the recursive solution

Question

I understand the recursion and find it useful and intuitive while solving problems on trees but for many other problems recursion never fails me to leave puzzled. Recently I was solving the following problem:

Write a recursive function that counts how many different ways you can make change for an amount, given a list of coin denominations.

After trying hard and some Googling I came up with the following solution and thinking about it in details makes me dizzy.

function isEmpty(coins) {
  return coins.length === 0;
}

function allButFirst(coins) {
  return coins.slice(1);
}

function countChange(money, coins) {
  if (money === 0) return 1

  else if (money > 0 && !isEmpty(coins)) {
    return countChange(money - coins[0], coins) +
      countChange(money, allButFirst(coins));
  }

  else // money < 0
    return 0;
}

console.clear();
console.log(countChange(4, [1, 2])); // 3 (1+1+1+1), (1+1+2), (2+2)

AFAIK, the first step in recursive solution is to check if the underlying structure is a recursive one which in my case it yes. But I is there some sort of principle of mental model or anything which could help in designing such solution, even something which could stop me going in wrong direction would work?

Answer 1

There are two problems here:

1. Make change for a given situation, and,
2. Permutate the given situation to find other answers.

These both together makes things rather confusing. So, you'll have to really try to keep these issues separate.

The first thing you should try to realize that result of any given invocation or level of the solution that you're looking for is a set or an array of answers, rather than a single answer, due to the permutation requirements.

If you factored out the permutations part, the resulting answer is a set of a count of coins by denominations, so already with a single best change answer, you have a a result type that is a set of pairs. When you then factor in the permutations, you have an array of those sets.

So, a solution should make perhaps the best possible answer (amount of change) for the situation, and then also permutate the situation so that another answer can appear. I would submit that these would end up as different parts of the the code. For example, when you traverse a tree ("in order"), you start: (1) traverse left, then (2) work self, then (3) traverse right. Each of these steps is clearly visible as distinguished from each other in the code.

Lastly, the permutations need to limit the amount of coins of each type otherwise, I don't think you'll hit all the permutations. So, the input needs to describe denominations and both either infinite quantity or limited quantity. Then a permutation can limit quantity first, then only limit denominations (which naturally falls out of quantity becoming limited to zero).

In short, you need to seriously inspect the type or shape of the result you're expecting for such a problem, and, similar to be said for the type or shape of the input you're providing.

(Also, you're working in a language that has limited type assistance, whereas if you were in C# or Java you'd get good help from the language and compiler about proper types.)

Answer 2

The way to create a recursive algorithm is as follows...

First write a function that solves for the simplest case. Then solve for the next simplest case by first reducing it to the simplest case and then call the function again for the simplest case.

Assume for this problem that the coins are in denominations 1, 5, 10, 25.

So first write a function that returns all the ways one can make change for 0 and errors out in any other situation. (Change for 0 would, of course, be an empty array of coins.)

Then change the function so it can make change for 1, then 2, then 3, up to 4. (In each case, there is only one solution, a single array of 1s that total the amount submitted.

Then the first interesting one... Make change for 5, here the function should produce two arrays. One containing [5] and the other containing [1] + makeChange(4).

The next interesting one... Make change for 10. Now it should return [[10], [5] + makeChange(5), [1] + makeChange(9)]

And so on...