How to return all combinations of N coin flips using recursion?

Question

Request:

Using JavaScript, write a function that takes an integer. The integer represents the number of times a coin is flipped. Using recursive strategies only, return an array containing all possible combinations of coin flips. Use "H" to represent heads and "T" to represent tails. The order of combinations does not matter.

For example, passing in "2" would return: ["HH", "HT", "TH", "TT"]

Context:

I am relatively new to JavaScript as well as the concept of recursion. This is purely for practice and understanding, so the solution does not necessarily need to match the direction of my code below; any useful methods or other ways of thinking through this are helpful, as long as it's purely recursive (no loops).

Attempt:

My attempt at this started out simple however the "action" progressively got more convoluted as I increased the input. I believe this works for inputs of 2, 3, and 4. However, inputs of 5 or higher are missing combinations in the output. Many thanks in advance!

function coinFlips(num){
  const arr = [];
  let str = "";

  // adds base str ("H" * num)
  function loadStr(n) {
    if (n === 0) {
      arr.push(str);
      return traverseArr();
    }
    str += "H";
    loadStr(n - 1);
  }
  
  // declares start point, end point, and index to update within each str
  let start = 0;
  let end = 1;
  let i = 0;

  function traverseArr() {

    // base case
    if(i === str.length) {
      console.log(arr);
      return arr;
    }

    // updates i in base str to "T"
    // increments i
    // resets start and end
    if(end === str.length) {
      str = str.split('');
      str[i] = "T";
      str = str.join('');
      i++;
      start = i;
      end = i + 1;
      return traverseArr();
    }

    // action
    let tempStr = str.split('');
    tempStr[start] = "T";
    tempStr = tempStr.join('');
    if(!arr.includes(tempStr)){
      arr.push(tempStr);
    };
    tempStr = tempStr.split('');
    tempStr.reverse();
    tempStr = tempStr.join('');
    if(!arr.includes(tempStr)){
      arr.push(tempStr);
    };

    tempStr = str.split('');
    tempStr[end] = "T";
    tempStr = tempStr.join('');
    if(!arr.includes(tempStr)){
      arr.push(tempStr);
    };
    tempStr = tempStr.split('');
    tempStr.reverse();
    tempStr = tempStr.join('');
    if(!arr.includes(tempStr)){
      arr.push(tempStr);
    };

    tempStr = str.split('');
    tempStr[start] = "T";
    tempStr[end] = "T";
    tempStr = tempStr.join('');
    if(!arr.includes(tempStr)){
      arr.push(tempStr);
    };
    tempStr = tempStr.split('');
    tempStr.reverse();
    tempStr = tempStr.join('');
    if(!arr.includes(tempStr)){
      arr.push(tempStr);
    };

    // recursive case
    start++;
    end++;
    return traverseArr();
  }

  loadStr(num);
}

coinFlips(5);

Answer 1

Below is a long description about how to create such recursive functions. I think the steps described help solve a great number of problems. They are not a panacea, but they can be quite useful. But first, here's what we'll work toward:

const getFlips = (n) =>
  n <= 0
    ? ['']
    : getFlips (n - 1) .flatMap (r => [r + 'H', r + 'T'])

---

Determining our algorithm

To solve a problem like this recursively, we need to answer several questions:

What value are we recurring on?

For simple recursions, it's often a single numeric parameter. In all cases there must be a way to demonstrate that we are making progress toward some final state.

This is a simple case, and it should be pretty obvious that we want to recur on the number of flips; let's call it n.

When does our recursion end?

We need to stop recurring eventually. Here we might consider stopping when n is 0 or possibly when n is 1. Either choice could work. Let's hold off on this decision for a moment to see which might be simpler.

How do we convert the answer from one step into the answer for the next?

For recursion to do anything useful, the important part is calculating the result of our next step based on the current one.

(Again, there are possible complexities here for more involved recursions. We might for instance have to use all the lower results to calculate the next value. For an example look up the Catalan Numbers. Here we can ignore that; our recursion is simple.)

So how do we convert, say ['HH', 'HT', 'TH', 'TT'] into the next step, ['HHH', 'HHT', 'HTH', 'HTT', 'THH', 'THT', 'TTH', 'TTT']? Well if we look at the next result closely, we can see that the in first half all elements begin with 'H' and in the second one they begin with 'T'. If we ignore the first letters, each half is a copy of our input, ['HH', 'HT', 'TH', 'TT']. That looks very promising! So our recursive step can be to make two copies of the previous result, the first one with each value preceded by 'H', the second one by 'T'.

What is the value for our base case?

This is tied to the question we skipped. We can't say what it ends on without also knowing when it ends. But a good way to make the determination for both is to work backward.

To go backward from ['HHH', 'HHT', 'HTH', 'HTT', 'THH', 'THT', 'TTH', 'TTT'] to ['HH', 'HT', 'TH', 'TT'], we can take the first half and remove the initial 'H' from each result. Let's do it again. From ['HH', 'HT', 'TH', 'TT'], we take the first half and remove the initial 'H' from each to get ['H', 'T']. While that might be our stopping point, what happens if we take it one step further? Taking the first half and removing the initial H from the one remaining element leaves us just ['']. Does this answer make sense? I'd argue that it does: How many ways are there to flip the coin zero times? Just one. How would we record it as a string of Hs and Ts? As the empty string. So an array containing just the empty string is a great answer for the case of 0. That also answers our second question, about when the recursion ends. It ends when n is zero.

Writing code for that algorithm

Of course now we have to turn that algorithm into code. We can do this in a few steps as well.

Declaring our function

We write this by starting with a function definition. Our parameter is called n. I'm going to call the function getFlips. So we start with

const getFlips = (n) =>
  <something here>

Adding our base case.

We've already said that we're going to end when n is zero. I usually prefer to make that a little more resilient by checking for any n that is less than or equal to zero. This will stop an infinite recursion if someone passes a negative number. We could instead choose to throw an exception in this case, but our explanation of [''] for the case of zero seems to hold as well for the negative values. (Besides, I absolutely hate throwing exceptions!)

That gives us the following:

const getFlips = (n) =>
  n <= 0
    ? ['']
    : <something here>

I choose here to use the conditional (ternary) expression instead of if-else statements because I prefer working with expressions over statements as much as possible. This same technique can easily be written with if-else instead if that feels more natural to you.

Handling the recursive case

Our description was to "make two copies of the previous result, the first one with each value preceded by 'H', the second one by 'T'." Our previous result is of course getFlips (n - 1). If we want to precede each value in that array with 'H', we're best using .map. We can to id like this: getFlips (n - 1) .map (r => 'H' + r). And of course the second half is just getFlips (n - 1) .map (r => 'T' + r). If we want to combine two arrays into one, there are many techniques, including .push and .concat. But the modern solution would probably be to use spread parameters and just return [...first, ...second].

Putting that all together, we get this snippet:

const getFlips = (n) =>
  n <= 0
    ? ['']
    : [...getFlips (n - 1) .map (r => 'H' + r), ...getFlips (n - 1) .map (r => 'T' + r)]


console .log (getFlips (3))

Examining the results

We can test this on a few cases. But we should be fairly convinced by the code. It seems to work, it's relatively simple, there are no obvious edge cases missing. But I still see a problem. We're calculating getFlips (n - 1) twice, for no good reason. In a recursive situation that it usually quite problematic.

There are several obvious fixes for this. First would be to give up my fascination with expression-based programming and simply use if-else logic with a local variable:

Replace conditional operator with if-else statements

const getFlips = (n) => {
  if (n <= 0) {
    return ['']
  } else {
    const prev = getFlips (n - 1)
    return [...prev .map (r => 'H' + r), ...prev .map (r => 'T' + r)]
  }
}

(Technically, the else isn't necessary, and some linters would complain about it. I think the code reads better with it included.)

Calculate a default parameter to use as a local variable

Another would be to use a parameter default value in the earlier definition.

const getFlips = (n, prev = n > 0 && getFlips (n - 1)) =>
  n <= 0
    ? ['']
    : [...prev .map (r => 'H' + r), ...prev .map (r => 'T' + r)]

This might rightly be viewed as over-tricky, and it can cause problems when your function is used in unexpected circumstances. Don't pass this to an array's map call, for instance.

Rethink the recursive step

Either of the above would work. But there is a better solution.

We can also write much the same code with a different approach to the recursive step if we can see another way of turning ['HH', 'HT', 'TH', 'TT'] into ['HHH', 'HHT', 'HTH', 'HTT', 'THH', 'THT', 'TTH', 'TTT']. Our technique was to split the array down the middle and remove the first letters. But there are other copies of that base version in the version of the array without one of their letters. If we remove the last letters from each, we get ['HH', 'HH', 'HT', 'HT', 'TH', 'TH', 'TT', 'TT'], which is just our original version with each string appearing twice.

The first code that comes to mind to implement this is simply getFlips (n - 1) .map (r => [r + 'H', r + 'T']). But this would be subtly off, as it would convert ['HH', 'HT', 'TH', ' TT'] into [["HHH", "HHT"], ["HTH", "HTT"], ["THH", "THT"], [" TTH", " TTT"]], with an extra level of nesting, and applied recursively would just yield nonsense. But there is an alternative to .map that removes that extra level of nesting, .flatMap.

And that leads us to a solution I'm very happy with:

const getFlips = (n) =>
  n <= 0
    ? ['']
    : getFlips (n - 1) .flatMap (r => [r + 'H', r + 'T'])

console .log (getFlips (3))

Answer 2

In case this is of any interest, here's a solution that doesn't use recursion as such but make use of the Applicative type.

---

Except when n is 1, the list of all possible combinations is obtained by combining all possible outcomes of each coin flip:

• 2² → [H, T] × [H, T] → [HH, HT, TH, TT]
• 2³ → [H, T] × [H, T] × [H, T] → [HHH, HHT, HTH, HTT, THH, THT, TTH, TTT]
• ...

A function that can take n characters and concat them can be written as such:

const concat = (...n) => n.join('');

concat('H', 'H');           //=> 'HH'
concat('H', 'H', 'T');      //=> 'HHT'
concat('H', 'H', 'T', 'H'); //=> 'HHTH'
//...

A function that produces a list of outcomes for n coin flips can be written as such:

const outcomes = n => Array(n).fill(['H', 'T']);

outcomes(2); //=> [['H', 'T'], ['H', 'T']]
outcomes(3); //=> [['H', 'T'], ['H', 'T'], ['H', 'T']]
// ...

We can now sort of see a solution here: to get the list of all possible combinations, we need to apply concat across all lists.

However we don't want to do that. Instead we want to make concat work with containers of values instead of individual values.

So that:

concat(['H', 'T'], ['H', 'T'], ['H', 'T']);

Produces the same result as:

[ concat('H', 'H', 'H')
, concat('H', 'H', 'T')
, concat('H', 'T', 'H')
, concat('H', 'T', 'T')
, concat('T', 'H', 'H')
, concat('T', 'H', 'T')
, concat('T', 'T', 'H')
, concat('T', 'T', 'T')
]

In functional programming we say that we want to lift concat. In this example I'll be using Ramda's liftN function.

const flip = n => {
  const concat = liftN(n, (...x) => x.join(''));
  return concat(...Array(n).fill(['H', 'T']));
};

console.log(flip(1));
console.log(flip(2));
console.log(flip(3));
console.log(flip(4));

<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.27.1/ramda.min.js"></script>
<script>const {liftN} = R;</script>

Answer 3

function getFlips(n) {
    // Helper recursive function
    function addFlips(n, result, current) {
        if (n === 1) {
            // This is the last flip, so add the result to the array
            result.push(current + 'H');
            result.push(current + 'T');
        } else {
            // Let's say current is TTH (next combos are TTHH and TTHT)
            // Then for each of the 2 combos call add Flips again to get the next flips.
            addFlips(n - 1, result, current + 'H');
            addFlips(n - 1, result, current + 'T');
        }
    }
    // Begin with empty results
    let result = [];
    // Current starts with empty string
    addFlips(n, result, '');
    return result;
}