Recursion – Designing Recursive Solutions in JavaScript

algorithmsdata structuresfunctional programmingjavascriptrecursion

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?

Best Answer

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.)

Related Topic