Oh, recursion.

There are two types of people, those who understand recursion and those who understand that there are two types of people in the world… (r/ProgrammerHumor)

But really. There seem to be people who can very naturally digest the concept of recursion, and those whose brains absolutely reject it. I happened to be one of the latter. In this post, we’ll go over recursion generally, and then work through a diagrammed problem example.

What is recursion?

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). (Source).

Recursion is a function that calls itself. Following the above, that function would be the ‘smaller instance’ of the larger problem. The larger problem is solved through repeated application of the functional solution to the smaller problem.

I found (and still find) it very helpful to diagram and understand exactly what everything is doing. If you’re struggling with internalizing the concept of recursion, I hope you find this post helpful.

First, one of the first breakthrough moments I had in understanding recursion came from watching the video below (‘What on Earth is Recursion‘ – Computerphile).

Example problem

One early problem I diagrammed to work through was to find a recursive solution that returns all the possible rock-paper-scissors play possibilities for ‘n’ number of play rounds.

[Edit: 4/13/2016]: Example solutions added for clarity:

n = 0 //=> []

n = 1 //=> ['r', 'p', 's']

n = 2 //=> ['rr', 'rp', 'rs', 'pr', 'pp', 'ps', 'sr', 'sp', 'ss']

(h/t TJ Martin for suggesting!)

First, the code:

function rockPaperPermutation (roundCount) {
  var results = [], actions = ['r', 'p', 's'];

  if (roundCount === 0) { return results; }

  else {

    var build = function(string) {
      if (string.length === roundCount) {
      for (var i = 0; i < actions.length; i++) {
        build(string + actions[i]);

  return results;

Let’s step through it. While I haven’t covered every mechanic in detail, the point is to get an idea for the flow.

Let’s kick off the recursion.


The ‘if’ check fails, so that block is skipped. We enter a ‘for’ loop (denoted below in green) through the ‘actions’ array (aka all of our available plays) and issue a recursive call to our ‘build’ function.


The ‘if’ check fails for string ‘r’, so code inside the ‘if’ block is skipped. We enter a new ‘for’ loop (denoted below in red) through the ‘actions’ array.


The ‘if’ check passes for ‘rr’, so following the code in the ‘if’ statement, we push the string ‘rr’ to the results array. Because of our ‘return’ included in the ‘if’ statement, no new loop is created, and we return back to the ‘red’ loop.


Continuing through the red loop, we check the string ‘rp’. It passes the check, so we push the string ‘rp’ to our results array, and then continue on through the red loop.


Continuing through the red loop, we check the string ‘rs’. It passes the check, so we push the string ‘rs’ to our results array, and continue through the red loop.


We have reached the end of the red loop, so we return back to the outer (‘green’) loop.


Following the same pattern as above, the ‘if’ check for (i = 1) in the green loop fails. A new for loop (denoted in blue) is initiated.


As before, the check for the string ‘pr’ passes, and the string ‘pr’ is pushed into the results array. We then return back into continuing on through our blue loop.


Strings ‘pp’ and ‘ps’ pass the check, and are pushed into the results array.


We have reached the end of our blue loop, and return back into continuing on through the green loop.


Following the same pattern as before, the ‘if’ check fails for string ‘s’, we enter a new for loop (here in purple), and find ourselves with the strings ‘sr’, ‘sp’, and ‘ss’ getting pushed into our results array.


We have reached the end of our purple loop, and return back out to the green loop. But, we have also reached the end of our green loop! That work is done. All that’s left now is to return the results array (noted in yellow).



Diagramming and whiteboarding are essential in learning and keeping flows straight. I have found it immensely helpful, as I hope you found the above to be helpful.

Leave a Reply

Your email address will not be published. Required fields are marked *