## JavaScript Recursive Combination Generator Function

March 20th 2020

Recursion is a powerful programming methodology but it can seem “magical” at times. In JavaScript recursion works by queuing all of the recursion calls into a call stack and when the base case evaluates to true the call stack “unwinds” and executes all of the recursion calls in the stack starting from the last (most recent) call to the first call. We will walk through what this looks like by reviewing the Rock Paper Scissor combination example using recursion.

The Rock Paper Scissor combination problem is:

Imagine you are playing a game of Rock Paper Scissors and you are playing 5 rounds. Write a function that returns an array of all the possible “plays” (also known as throws) that you could have in those 5 rounds. One element of an array would be a string representing one possible solution ie. “RPSSR” which represents you throwing “Rock, Paper, Scissors, Scissors, Rock”. If there are 3 possibilities for every “throw” and you are playing 5 rounds you could have a total of 243 different solutions: 3 to the fifth power (3^5).

The function that we are writing will take a number of rounds that we are playing so it’s scalable to 3 rounds or 5 rounds or even 10 rounds! Let’s stub out our Rock Paper Scissor combination function:

``````const rockPaperScissors = (rounds) => {
//if rounds is 0 we will return an empty array
if(rounds === 0) return []

// define a throw options array for each play we could make
// "R" represents "Rock", "P" represents "Paper", "S" represents "Scissors"
const throwOptions = ["R", "P", "S"]
// define a solutions array to hold all of our possible solutions
const solutions = []

// return the solutions array
return solutions
}``````

In our function we are handling the edge case that someone passed in `0` rounds so we are just returning and empty array. We are defining a `throwOptions` array which represents each “throw” or play we could make in our game. Finally, we’re defining a `solutions` array that we are going to use to store all of our possible solutions; this is the array that we will return at the end of our function.

Our next order of business is to create our recursion function which performs the bulk of the work for our combination generator. Our `combinations` function will take one argument which is a string that represents one possible solution (which will eventually be pushed to our `solutions` array). The string will be initialized to an empty string if it is not defined:

``````const rockPaperScissors = (rounds) => {
//if rounds is 0 we will return an empty array
if(rounds === 0) return []

// define a throw options array for each play we could make
// "R" represents "Rock", "P" represents "Paper", "S" represents "Scissors"
const throwOptions = ["R", "P", "S"]
// define a solutions array to hold all of our possible solutions
const solutions = []

const combinations = (solution = '') => {

}

// return the solutions array
return solutions
}``````

Now we need to define our base case so that our recursive function will stop once it hits this base case and return. Our base case conditional will check to see if the length of our `solution` argument is equal to the number of rounds that we’re playing. If it is then we know that we have hit one possible solution and we can add that to the `solutions` array. An example would be “RPPSR” as the length would equal 5 (5 plays === 5 rounds) and we know we have a possible solution:

``````const rockPaperScissors = (rounds) => {
//if rounds is 0 we will return an empty array
if(rounds === 0) return []

// define a throw options array for each play we could make
// "R" represents "Rock", "P" represents "Paper", "S" represents "Scissors"
const throwOptions = ["R", "P", "S"]
// define a solutions array to hold all of our possible solutions
const solutions = []

const combinations = (solution = '') => {
//base case definition
if(solution.length === rounds){
return solutions.push(solution)
}
}

// return the solutions array
return solutions
}``````

Now that we have our base case conditional in place for our combinations function we can continue to define the next part of our function. We will want to loop through all of our `throwOptions` and recursively call our `combinations` function passing in the current `solution` string plus the current element we’re iterating over such that our function looks like:

``````const rockPaperScissors = (rounds) => {
//if rounds is 0 we will return an empty array
if(rounds === 0) return []

// define a throw options array for each play we could make
// "R" represents "Rock", "P" represents "Paper", "S" represents "Scissors"
const throwOptions = ["R", "P", "S"]
// define a solutions array to hold all of our possible solutions
const solutions = []

const combinations = (solution = '') => {
//base case definition
if(solution.length === rounds){
return solutions.push(solution)
}
throwOptions.forEach(option => {
combinations(solution + option)
})
}

// return the solutions array
return solutions
}``````

Finally, we will want to invoke the first iteration of our `combinations` function:

``````const rockPaperScissors = (rounds) => {
//if rounds is 0 we will return an empty array
if(rounds === 0) return []

// define a throw options array for each play we could make
// "R" represents "Rock", "P" represents "Paper", "S" represents "Scissors"
const throwOptions = ["R", "P", "S"]
// define a solutions array to hold all of our possible solutions
const solutions = []

const combinations = (solution = '') => {
//base case definition
if(solution.length === rounds){
return solutions.push(solution)
}
throwOptions.forEach(option => {
combinations(solution + option)
})
}

combinations()

// return the solutions array
return solutions
}``````

Now once we run our function passing in the number of rounds we are playing we will get the total combination of options we could play `rockPaperScissors(5)`

``(243) ["RRRRR", "RRRRP", "RRRRS", "RRRPR", "RRRPP", "RRRPS", "RRRSR", "RRRSP", "RRRSS", "RRPRR", "RRPRP", "RRPRS", "RRPPR", "RRPPP", "RRPPS", "RRPSR", "RRPSP", "RRPSS", "RRSRR", "RRSRP", "RRSRS", "RRSPR", "RRSPP", "RRSPS", "RRSSR", "RRSSP", "RRSSS", "RPRRR", "RPRRP", "RPRRS", "RPRPR", "RPRPP", "RPRPS", "RPRSR", "RPRSP", "RPRSS", "RPPRR", "RPPRP", "RPPRS", "RPPPR", "RPPPP", "RPPPS", "RPPSR", "RPPSP", "RPPSS", "RPSRR", "RPSRP", "RPSRS", "RPSPR", "RPSPP", "RPSPS", "RPSSR", "RPSSP", "RPSSS", "RSRRR", "RSRRP", "RSRRS", "RSRPR", "RSRPP", "RSRPS", "RSRSR", "RSRSP", "RSRSS", "RSPRR", "RSPRP", "RSPRS", "RSPPR", "RSPPP", "RSPPS", "RSPSR", "RSPSP", "RSPSS", "RSSRR", "RSSRP", "RSSRS", "RSSPR", "RSSPP", "RSSPS", "RSSSR", "RSSSP", "RSSSS", "PRRRR", "PRRRP", "PRRRS", "PRRPR", "PRRPP", "PRRPS", "PRRSR", "PRRSP", "PRRSS", "PRPRR", "PRPRP", "PRPRS", "PRPPR", "PRPPP", "PRPPS", "PRPSR", "PRPSP", "PRPSS", "PRSRR", …]``

There you have it! We used recursion to create a combination generator function in JavaScript. Hope this will help with your next combination project. Until next time, stay curious, stay creative.