Recursion for Idiots Like Me

February 28, 2024

Most software developers will likely come across the topic of recursion at some point in their career. In a large percentage of cases, this will probably be during a job interview. Recursive functions and their applications are a favorite at the old whiteboard. I recently implemented a recursive function in practice, and the process of designing the function caused me to step back and re-teach myself about recursive functions in general. In this post, I will walk through three common problems and three recursive solutions. As always, these solutions are almost certainly not the best. But they work, damn it.

Background - Functions Can Call Themselves(!?)

There are a few different definitions of recursion out there, but I think the simplest one is found at good ol' Wikipedia: "Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself." This is a pretty heady concept, and it can really challenge one's mental model of function definitions and invocations in Javascript. A function can see outside itself and call itself and pass arguments to itself? What? But how does the function even know that it exists? The answer has to do with how the Javascript engine sets up its runtime and hoists values, but the takeaway is that the below is totally fine:

function foo(arg) {
  return foo(otherArg)
}

Now as written this would cause an infinite loop and crash the program. But it is valid.

Alright, this sounds horrible and overly complex. Why would we want to do this? Recursion can help with breaking problems down and avoiding unnecessary loops. It's especially helpful if you've got a dataset that is recursive in itself (nested data sets of unknown length/depth).

Some will argue recursion improves readability, though I think this is highly situational. My view is that using a recursive function on the front end is probably a sign that whatever logic you're performing belongs somewhere else (the API? Some service?).

So reaching for a fancy recursive solution to any given problem is likely not the right approach. But if you find yourself in a mess of nested loops, it might be something to consider.

Ground Rules: Always Have an Escape Hatch

In the code example above, I mentioned that running the code would cause an inifite loop. The function would just call itself over and over. There's no code here telling it to stop.

function foo(arg) {
  return foo(otherArg)
}

It's crucial to establish a case or cases when recursion should stop. Approaching your problem with the "escape hatch" first mentality will ensure you don't crash your program when you run your function, and it will help to better frame the problem you're trying to solve. It makes you consider what conditions are changing between function calls and what the ultimate GOAL of the function actually is.

function foo(arg) {
  if (!someCondition) {
    return arg
  }
  // Do some work here that ensures that otherArg changes...
  return foo(otherArg)
}

Let's try some examples...

Countdown From n

Prompt: Write a recursive function that counts backwards from n to 1.

Now this type of problem could obviously be done with a simple for loop. For readability and predictibility, I think that's what one would naturally do if presented with such a problem. We but we can also do this recursively, and the solution is definitely more elegant.

What is our escape hatch?: We know that the function should stop counting once it reaches 1. Therefore, we can add a check at that point in the function's evaluation to stop the recursion.

 function countDown(n) {
  if (n ===1) {
    return;
  }
 }

Right, so we've established our escape hatch that will cause the function to exit safely. Next, what work do we want to do to ensure that we're not just passing the same argument into the function with each call? In this case, it's pretty simple. We want to log the value and then decrement it for the next call.

 function countDown(n) {
  if (n === 1) {
    return;
  }

  console.log(n);

  countDown(n - 1);
 }

This example works and meets Ground Rules established above: we've got an escape hatch and we're changing arguments between function calls.

Fibonacci Sequence

Prompt: Write a recursive function that finds the value of n in a Fibonacci sequence.

We're all familiar with the Fibonacci sequence, be it from bad Dan Brown novels or inaccurate attempts to size the work effort of tech initiatives. Regardless, the ol' fib sequence is generally used as an example of recursion in mathematics. The definition is generally given as:

f(n) = f(n-1) + f(n-2) for n > 1

Recall that Fibonacci sequence is defined as follows:

0 1 1 2 3 5 8 13 21 ...

The formula above is intended to find the value at n in the squence:

f(3) = 1 f(4) = 2; f(5) = 3;

So how would we translate this to javascript? Notice that the definition given above already gives us our escape hatch for free:

for n > 2

So there are many ways to write this. Here's one:

function fibAt(n) {
  if (n > 2) {
    return fibAt(n-1) + fibAt(n-2)
  }
  return n
}

This is obviously a bit more involved than the simple countdown example. What we're doing is essentially whittling down a number until it hits our escape hatch. Eventually we are just going to be returning the number 1 added together a bunch of times. We have to kind of "flatten" the value until it meets our condition to actually be returned. Something like:

o = test passed, hit escape hatch, return safely
x = haven't hit escape hatch, keep doing work
x
xx
xxx
xxxx
xxxxxo
xxxxoo
xxoooo
xooooo
oooooo

Speaking of flattening...

Array Flattening

Prompt: Flatten this array. Do not use a library.

At one point in the Front End world this was a classic interview question. It probably still is. The intention of the question is basically to see if the candidate goes into an undending hell of nested loops and type checks, or if they have read a blog post about common interview questions and simply memorized a recursive solution.

Anyhoo, I think array flattening is a great example of a practicle application of recursion. It's very common, at least in my experience, to flatten nested data structures from the API. Why not do it yourself and skip the library?

So we know we have to be able to deal with theoretically infinitely deep arrays. And they can contain all sorts of things:

 const arrayFromHell = [1,[2], [[3]], 4, [[[{number: 5}]]]];

So what is our escape hatch here? What point are we trying to get to where we no longer need to recurse or do any more work?

function flatten(arr) {
  arr.iterateSomehow()...
  // When can we stop flattening?
  return flatten(...)
}

We need to get from

[1,[2,3],[[[4]]]]

[1,2,3,4]

Looking at the difference in values above, we can see that the result no longer has any nested arrays within it. That is, we can stop doing work on each element in the original array when a given element is no longer an array at all...

So our test might look something like this:

const escapeHatch = (el) => !Array.isArray(el);

With that in mind, let's look at two solutions here. The first makes use of closure and vanilla for loops:

function flattenArray(arr) {
    const flattened = [];
    const escapeHatch = (el) => !Array.isArray(el);

    function recursiveHelper(arr) {
        for (let i = 0; i < arr.length; i++) {
            if (escapeHatch(arr[i])) {
              flattened.push(arr[i])
            } else {
              recursiveHelper(arr[i]);
            }
        }
    }

    recursiveHelper(arr);
    return flattened;
}

Here we make use of JS closure to create an empty array in the outer scope of the function. Our inner recursiveHelper function then checks each element. If it's not an array, we can push it to the flattened list. If it's still an array, we have to keep doing work until it's not.

A fancier and more compact solution might look like the below. We use a reduce function to eliminate the need for an array to push to, and we make use of [...spread] operators.

 function flatten(arr) {
  return arr.reduce((acc, cur) => {
    const escapeHatch = !Array.isArray(cur);
    if (escapeHatch) {
      return [...acc, cur]
    } 
    return flatten([...acc, ...cur])
  }, [])
 }

Both solutions solve the problem in a similar way: keep digging down into the array until we find an element that is NOT an array itself.

Parting Thoughts

I've always come back to the above three examples whenever I need to refresh my brain on the concept of recursion. I hope this helps!

Frontend Dad Blog.