Recursive Functions for Working Developers

Exploring the basic building blocks of recursive functions in JavaScript in an easy and intuitive way.

Because many of us developers are struggling to understand recursive functions, we shy away from using them like they’re Pandora's Box and resort to imperative code (the familiar for and while loops) just to get the job done. That’s a shame because there are many benefits in understanding and writing recursive code, one of which can make us better programmers. This post will shine a new light on recursive functions by dividing them into basic building blocks or scaffoldings that are easy for anyone to reapply when writing other more complicated recursive functions using the accessible JavaScript Language.

A recursive length

Take a look at the function length that calculates the length of an array similar to Arr.length , written in a recursive fashion:

function length(arr) {
  if (arr.length === 0) {
    return 0;
  } else {
    const t = arr.slice(1, arr.length)
    return 1 + length(t);
  }
}

To start writing any recursive function, we need to start with the key part — The base case — or when the function terminates. In logic, the base case is known as an axiom — something that is held true without the need for further proof or argument. When writing a recursive function, we have to ask ourselves about this base case, or what we know as the ultimate truth.

In the case of this length function, we can infer the base case as “If the array is empty, then the length is 0.” It makes perfect sense for length to return 0 when arr is an empty array. The base case resides in the if block.

It might be a little weird to call the method arr.length in the code. In JavaScript, one cannot simply assert arr === [] to determine an empty array arr .

Now comes the second most important part of the function — the inductive case. This piece of code usually has two subparts to it:

1. The inductive part — In this case decreasing arr by one toward an empty array, and retrieve a pointer to it as per line 5.
2. The recursive part — Which is divided into two subparts:

• The head is what we want to accumulate over time. In this case, we want to add 1 to count each time we encounter it and decrease arr it by one.
• The tail call to length itself with the decreased array as an argument.

Each recursive call to itself, length(t) takes an argument of an array with one less member, while 1 is added to every member less. The inductive case resides in the else block.

A Function That Collects

To make it a little more challenging, let’s write a function called sSplitthat splits a string into individual characters. Here is a scaffold with the key parts left as comments:

function sSplit(str) {
  if (str === "") {
    // Base case here.
  } else {
    // Inductive case here.
  }
}

Let’s think about the base case, or what makes sense for sSplit to return in the face of an empty string. There is nothing to do except return an empty array of characters, so that’s what sSplit should return for the base case.

The inductive case is a little tricky, but let’s stick to our framework and see what happens.

The inductive part

We want to decrease the string str bit by bit to reach the base case of an empty string. This means “chomping” on the first character of the current string with str.slice(1, str.length) , which slices the string from the second character to the end of that string, omitting the first character. However, in this case, we also want to collect each omitted character because, in the end, we are returning an array of individual characters. Thus, we want to keep the first character around for the next part.

Now our function looks like this:

function sSplit(str) {
  if (str === "") {
    return [];
  } else {
    const [h, t] = [str.charAt(0), str.slice(1, str.length)];
  }
}

We use fancy pattern matching in JavaScript to extract the first character and the rest of the string in one single line. h now stores the first letter of the current str while t stores the rest of the string, minus the first letter.

The Recursive Part

As mentioned earlier, the recursive part is divided into two subparts — head and tail. In the head, we want to do something that accumulates over time. In this case, perhaps to store each individual character in an array. Now, unlike a for or while loop where we usually have a global array outside of the loop and push each character to it, in a stateless recursive function we don’t have that luxury. How do we carry over or persist something in memory? We simply do it in the function’s argument. This pattern of persisting storage as an extra argument in a recursive function is known as an accumulator.

Now we modify the sSplit function to accept an array as an extra optional argument:

function sSplit(str, arr = []) {
  if (str === "") {
    return [];
  } else {
    const [h, t] = [str.charAt(0), str.slice(1, str.length)];
  }
}

Now we can use arr as our persistence. In the tail part, calling the function itself with str one character less and arr one character more:

function sSplit(str, arr = []) {
  if (str === "") {
    return [];
  } else {
    const [h, t] = [str.charAt(0), str.slice(1, str.length)];
    return sSplit(t, arr.concat([h]));
  }
}

We could have easily called arr.push(h) before calling sSplit(t, arr) but it modifies the original array which makes the code longer and harder to reason about. arr.concat([h]) returns a new array from two concatenated arrays, which is more functional but at some greater performance cost.

Take a hard look at the recursive call at line 6. t is being decreased by one character each time, and will eventually reach the base case where the string is empty. At that certain moment, what we want is to return the accumulator arr , which has been collecting characters over time.

What about the case when the string str is initially empty? Of course, sSplit should return an empty array as before. But because arr is already an empty array to begin with, we can safely return arr for all cases.

Here is our complete code for sSplit :

function sSplit(str, arr = []) {
  if (str === "") {
    return arr;
  } else {
    const [h, t] = [str.charAt(0), str.slice(1, str.length)];
    return sSplit(t, arr.concat([h]));
  }
}

Recap…

In this post, we examined the basic building blocks of a recursive function — which are the base and inductive cases — by building two useful recursive functions. In the second function, we also explore the accumulator pattern — which is persistence in recursive functions through the functions’ arguments.

I hope this post has been educating and helpful to all the readers trying to wrap their minds around recursive functions out there. Feedback is warmly welcomed, so please leave notes and comments to let me know what is helpful and what isn’t.