A Recursion Primer for Fools Like Me

After not programming for several years, I recently started relearning it as a student at Hack Reactor. Some techniques and ideas came back easier than others, but one of the hardest to wrap my head back around has been recursion.

It’s difficult to keep your head straight when dealing with multiple return values, variable changes over closure, and recursive function calls. That’s why I wrote this tutorial! Below, I’ve outlined the problem-solving process I follow for simple recursion problems, in pseudocode and in Javascript. If you’re unfamiliar with the concept of recursion, hopefully this can help you push through your problem set or project.

For example, let’s say we’re trying to write a recursive function that finds the digital root of an integer. In other words, it takes the digits of a number and adds them together. If that sum is one digit, we’re done. If that sum is more than one digit, it adds those digits together. If that new sum is one digit, we’re done. If that new sum is more than one digit, then it adds those new….

You get the idea.

var digitalRoot = function(n) {
  //We'll problem-solve here.
};

Step 1: Identify the “base case” using trivial input.

First, we need to identify our “base case,” or the conditions under which our function doesn’t need to recurse. I think the easiest way to do this is to just run some really simple values through our function.

In this case, we know that our digitalRoot function will take in an integer and put out an integer. We also know that the sum of digits for a single-digit number…is just itself. If we pass 1 into our function, we should just get 1. If we pass 2 into our function, we should just get 2. Let’s pseudocode it out.

var digitalRoot = function(n) {
  // if n is a single-digit number
    // return n
};

Step 2: Identify the recursive case.

By the inverse of our base case, we now know that: if n is any number with more than a single digit, we need to recurse. But exactly how are we going to recurse, and what are we going to pass into the function each time to get what we want? This is the tricky part.

var digitalRoot = function(n) {
  // if n is a single-digit number
    // return n
  // else if n has more than one digit
    //recursion here
};

Whenever I’m struggling to implement a function’s recursive case, I do exactly what we just did for the base case: I run a set of simple inputs through the function and observe how they change.

Step 3: Run trivial input through recursive case.

var digitalRoot = function(n) {
  // if n is a single-digit number
    // return n
  // else if n has more than one digit
    
  // digitalRoot(12) => 1+2 = 3
  // digitalRoot(40) => 4+0 = 4
  // digitalRoot(75) => 7+5 = 12 => digitalRoot(12) = 3
};

Hopefully, this is where we start to identify patterns. After writing it out like this, we can see start to see how it works: anytime n has two digits or more, we need to call digitalRoot on the sum of its digits. If we make it really explicit, it looks like this:

var digitalRoot = function(n) {
  // if n is a single-digit number
    // return n
  // else if n has more than one digit
    //return digitalRoot(sum of n's digits)
// digitalRoot(12) => digitalRoot(3) = 3
// digitalRoot(40) => digitalRoot(4) = 4
// digitalRoot(75) => digitalRoot(12) => digitalRoot(3) = 3    
};

Step 4: Consider any side constraints.

Now that we have the core of our function, what else do we need to get it to work? In this case, it’s taking the integer argument and accessing its individual digits so we can sum them. There are probably several ways to do this, but maybe the simplest is turning its digits into an array, then iterating over the array to sum the elements in it. JS has a built-in join method that turns a string into an array, so maybe we should convert it to a string first too.

var digitalRoot = function(n) {
  // if n is a single-digit number
    // return n
  // else if n has more than one digit    
    //make array of digits
    //return digitalRoot(sum of n's digits)
};

Step 5: Convert pseudocode to real code.

var digitalRoot = function(n) {
  if (n < 10) {
    return n;
  }
/*converts to a string, then to an array of chars, then to an
  array of integers using the Number wrapper object*/
  var str= n.toString();
  var stringDigits = str.split("");
  var digits = stringDigits.map(Number);
  var sum = digits.reduce((a, b) => a + b);
  return digitalRoot(sum);
};

We did it! Maybe we can refactor this to be more concise.

var digitalRoot = function(n) {
  if (n < 10) {
    return n;
  }
  var digits = n.toString().split("").map(Number)
  var sum = digits.reduce((a, b) => a + b);
  return digitalRoot(sum);
};

And more concise still . . .

function digitalRoot(n) {
  return n < 10 ? n : digitalRoot(n.toString().split("").map(Number).reduce((a, b) => a + b));
}

Nice.

It should be noted that truly complex recursion problems may need a more nuanced or lengthy approach. I just wanted to write this as a resource I wish I had a month or two ago, when I was a beginner and absolutely lost on even simple recursion functions. If you’re new to programming or struggling to grasp recursion, hopefully this gave you some new ideas! Happy coding.