Since being introduced to recursion, I've wanted to dig deeper into the subject and see the process more visually. Maybe if I can visualize it, it will come more naturally? So enough of kicking that can down the road... let's take the time to look at this recursion problem called Rock, Paper, Scissors!
With this Toy Problem, we are are given an input of n - which represents the number of rounds a single player will play paper, rock, scissors. We are asked to return every different possibility one person could throw as an array - and all of those arrays will be within one larger return array.
If we knew n, we could potentially skirt the rules and use nested loops, but alas... sounds like our old friends recursion. Put simply, recursion is when a function calls itself until it doesn't anymore...
Here, we're going to create an array and use a recursive function to build up that array until we return it at the end - let's get set up.
Boom. There's an array and there's a return statement for the array at the end, after we build it. What else would help? Well, let's throw an array out there that has all the possible throws - rock, paper, and scissors. Also, we know a recursive function is coming, so let's get that staged.
The other new things you might notice here are the actual function call on line 51 and the function parameters on line 46. Each result array that we are going to add to 'differentThrowCombos' to return will be built up from the empty array on line 51 by being inserted for the parameter of the recursive function. The roundsToGo is going to count down the rounds until it is decremented to zero, by which time it will be an array of 3 items and get pushed into the differentThrowCombos array.
So now let's see the magic! ...after we look at one more pic to see the recursive case. The loop will come to a close when 3 items have been concatenated into an array - we'll know this because the rounds have been decremented to 0. Let's push it to a results array! I feel someone will be upset if I don't utter "base case"...so there it is.
So, let's take a look at the recursion and then we can break it down a little further:
*For much of the following explanation, we will assume an 'n' of three - there are 3 rounds.
Let's talk briefly about what's going on here and then I'll share some diagrammed pics that may help you think about how the recursion is happening. There are 3 choices in the 'choicesOfThrow' array. We are using a forEach loop to cycle through those choices. 'thro' here is either going to be 'rock', 'paper', or 'scissors.
So, for whichever one of those we are currently looping on, we are going to recursively call the function for that value concatenated with the current array - which on the first level is just an array literal - so we are calling the function recursively with ['rock'] and the decremented roundsToGo of 2 -getCombos(['rock'], 2). This will go through the function again until it is sent back to function again as getCombos(['rock', 'rock'], 1).
While the paper and scissors portions are still waiting to go through the earlier forEach loops, the most recent loops keep executing. The rounds will go to zero for our first array of ['rock','rock','rock'] and it will reach the base case where it is pushed into the 'differentThrowCombos' array first. And now we can go back to the loop that has stalled at [rock, rock] and finish the forEach there - ['rock','rock','paper'] and ['rock','rock','scissors'] will be the next to be added to the 'differentThrowCombos' array. Then back to finish the the previous loop and so on.
Here is rock paper scissors in tree structure. Spend a few minutes looking at how we get the results in order from left to right. I feel like visualizing recursion has helped me tremendously and may help you too.
Top comments (0)