Recursion : Rock, paper, scissors

Every recursive function has to have the following features:

  1. A base or terminating case.
  2. A recursive case.
  3. Some progress made at each invocation of the recursive function.

Let’s take a look at a toy problem. Say we have 2 people in a game of rock, paper, scissors. And they play for n number of rounds. Write a recursive function that produces an array that contains arrays of all the different possibilities of the outcome.

var rockPaperScissors = function( numOfRounds ) {
var options = ['rock', 'paper', 'scissors'];
var allPossibilities = [];
  return allPossibilities;
}

So all possible permutations of outcomes for 2 rounds would be:

[ [ ‘rock’, ‘rock’ ], [ ‘rock’, ‘paper’ ], [ ‘rock’, ‘scissors’ ],
[ ‘paper’, ‘rock’ ], [ ‘paper’, ‘paper’ ], [ ‘paper’, ‘scissors’ ],
[ ‘scissors’, ‘rock’ ], [ ‘scissors’, ‘paper’ ], [ ‘scissors’, ‘scissors’ ] ]

Our rockPaperScissors function could have been a recursive function itself or we could define an inner function that we would use to be run recursively if the base condition is not met.

The following is the latter approach. Feel free to try the the former approach and share your solution with me! (It’s way more challenging in my opinion.)

var rockPaperScissors = function( numOfRounds ) {
var options = ['rock', 'paper', 'scissors'];
var allPossibilities = [];

var roundChoice = function() {
  }
  return allPossibilities;
}

One rule that I found to be really useful when creating a recursive function is to first determine what the base case is.

A base case is a scenario where a set condition is met which causes the recursive function to terminate. This usually comes in the form of an if statement.

var rockPaperScissors = function( numOfRounds ) {
var options = ['rock', 'paper', 'scissors'];
var allPossibilities = [];

var roundChoice = function(round, roundNumber) {
for(var i = 0; i < options.length; i++){
round.push(options[i]);
if(roundNumber === numOfRounds){
allPossibilities.push(round.slice());
}else{
roundChoice(round, roundNumber + 1);
}
}

}
roundChoice([], 1);

return allPossibilities;
}

In roundChoice we could iterate through the options array and populate an array (round) that would represent a single outcome with each option. For each recursively call to roundChoice, we increment roundNumber.

Our base case would be when roundNumber equals numOfRounds, where we will then populate allPossibilities array with the array that consists of a single possible outcome. Our recursive case is when roundNumber is less than numOfRounds.

There is still one piece of code that we are missing. We want to be able to remember to remove the last item of our round array before the next iteration in the for loop.

var rockPaperScissors = function( numOfRounds ) {
var options = ['rock', 'paper', 'scissors'];
var allPossibilities = [];

var roundChoice = function(round, roundNumber) {
for(var i = 0; i < options.length; i++){
round.push(options[i]);
if(roundNumber === numOfRounds){
allPossibilities.push(round.slice());
}else{
roundChoice(round, roundNumber + 1);
}
round.pop();
}
}
roundChoice([], 1);
return allPossibilities;
}

That’s it! Recursion can be really unintuitive and difficult to reason about and visualise at first. But as with every other skill, practice makes perfect. Just keep at it and I promise you’ll get the hang of it in no time.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.