Recursion

What is a recursive function?

Every once in a while, you'll need to code a recursive function. Even though you've heard the term, you might not have had the chance to implement one yet.

Let's start by defining what a recursive function is. The most straightforward answer is : a function that calls itself. Naturally, the next question is, When does it stop??

This is a crucial question because understanding when a recursive function stops is the most important concept to grasp. A recursive function needs what we call a base case, a condition that, when met, returns a value instead of calling itself again.

For example, let's say you want a function that prints only even values from an array. You might think, "I can just use a for loop," and you'd be right. It's generally the most straightforward way. However, when facing a complex problem, a common strategy is to split it into smaller subproblems. That's when recursion shines.

Conceptually, the main difference between recursion and an iterative approach is that you don't know how many iterations will take place. What you need to know is when it should stop, again, our base case. Otherwise, you'll run into an infinite loop and encounter an error message like this:

Maximum call stack reached.

Why does this happen? Whenever you call a function, its execution is pushed onto the call stack. When the function calls another function, its execution is added on top of the stack (think of it as a stack of dishes, the first one you stacked is the last one you'll clean). This process continues until the base case is met. If the base case is never met, you'll encounter the error:

Maximum call stack reached.

This indicates that there are too many functions on the stack, and its volume is increasing too fast for JavaScript to handle, signaling an infinite loop.

So always remember, before jumping to the coding part, define your base case.

The How-To

Now that you understand the importance of a base case, let's say you want to extract numbers from an array and aggregate them into another array. If you define the array inside the function call, it will start empty on every execution.

There are essentially two ways to handle this problem:

The aggregating way

With this method, you pass the aggregated array as a parameter so that you can keep filling it.

function aggregateWay(rows, arr = []) {
  if (!rows.length) return arr;
  arr.push(rows.pop().value);
  return aggregateWay(rows, arr);
}

The Outer Function Way

With this method, you create two function scopes. The outer one defines the array, and the inner one defines the recursive function itself. The inner function keeps calling itself until the base case is met.

function outerWay(rows) {
  const arr = [];

  function recursive(rows) {
    if (!rows.length) return;
    arr.push(rows.pop().value);
    return recursive(rows);
  }

  recursive(rows);
  return arr;
}

Whichever method seems more intuitive to you is essentially a matter of personal preference. However, the outer function way is usually easier to understand, especially if the logic is already complex.

Performance Considerations

While recursion can be a powerful tool, it's important to consider its performance implications. Recursive functions can be less efficient than iterative solutions due to the overhead of function calls and the risk of stack overflow. However, modern JavaScript engines optimize tail-recursive functions (A recursive function where the function calls itself at the end of the function in which no computation is done after the return of recursive call), which can help mitigate these issues. A tail-recursive function is one where the recursive call is the last operation in the function.

That's it for a quick introduction on recursive functions. I'll probably use them in future articles about common algorithms. If you learned something from this article or have anything else to add, feel free to comment below.

Happy coding ! 👨🏻‍💻