Recursion

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) {
        results.push(string);
        return;
      }
  
      for (var i = 0; i < actions.length; i++) {
        build(string + actions[i]);
      }
    };

    build('');
  }
  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.

recursion1

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.

recursion2

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.

recursion3

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.

recursion4

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.

recursion5

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.

recursion6

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

recursion7

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.

recursion8

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.

recursion9

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

recursion10

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

recursion11

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.

recursion12

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).

recursion13

 

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 *