Recursion with JavaScript - Pt. 2

Rock, Paper, Scissors

I went over the basics of recursion in a previous blog post. Time for something a little bit more advanced.

Rock, Paper, Scissors was a little problem requiring recursion that took me a bit longer than usual to grasp the first time I encountered something like it.

The problem is simple:

Write a function that generates all possible throws a single player could throw over a n-round game of rock-paper-scissors.

So if the player has to play 3 rounds, the result we want is:

[
  ["rock", "rock", "rock"],
    ["rock","rock","paper"],
    ["rock","rock","scissors"],
    ["rock", "paper", "paper"],
    ...and so on
]

What We Know

Before we start, let's think about the various inputs, outputs, and variables we'll need.

  1. We know our choices: rock, paper or scissors.

    We can put that in an array. Let's call it weapons: const weapons = ['rock', 'paper', 'scissors'];

  2. We know that we'll have to keep track of all possible hands. So let's have another variable called hands initialized as an empty array. This is what we will return. const hands = [];

  3. The function's input will be the number of rounds n. So we can only have n rounds and from that generate all possible hands.

  4. We know that there's gonna be some recursion.

Skeleton

With these things in mind, we can form the skeleton of the algorithm we'll need to write:

function rockPaperScissors(n) {
  const hands = [];
  const weapons = ['rock', 'paper', 'scissors'];

  function recurse() {
    if (some base case) {
        //something that ends the recursion
    } else {
        //magic!
    }
  };

  recurse(/* some input */);
  return hands;
}

This algorithm has to keep track of two different things: 1) how many rounds have been played and 2) all the possible combinations.

Base Case

Next thing is to come up with a base case for our recursion--when do we need it to stop?

Our base case will be when the number of rounds we are currently on (n) is equal to 0. Each possible hand cannot have more than n rounds. After all rounds have been played, we want to store that hand as a result and return out of the function.

Recursive Case

The recursive case is a little trickier. Because there are three possible weapons, we want to loop through each weapon and have each of those different plays go back through the recursive function, along with a decremented round-count.

This is kind of hard to explain through words and can only be visualized.

Here's the full code:

function rockPaperScissors(n) {
  let rounds = n;
  const results = [];
  
  const weapons = ['rock', 'paper', 'scissors'];
  
  function recurse(roundsLeft, played) {
    if(roundsLeft === 0) {
      results.push(played);
      return;
    }
    for(let i = 0; i < weapons.length; i++) {
      const current = weapons[i];
      recurse(roundsLeft-1, played.concat(current));
    }
  };
  recurse(rounds; []);
  return results;
}

This is really structured like a tree and each recursion that the function goes through shoots off down a branch on the tree. Because of the for-loop that goes over each weapon, three trees are created, with the starting node on rock, paper, and scissors, respectively. And using each tree, the function goes through all possible combinations.

At the end, this all joins together in the results variable.

Here's a diagram of one of the trees (the one starting with rock).

I hope my explanation makes sense. The best way to learn recursion is to write it all out from beginning to end.

This is one of my favorite little coding problems and I hope it becomes yours!