Recursion in Functional JavaScript

M. David Green
M. David Green
Share

You may have come across references to recursive functions while programming in JavaScript. You may even have tried to construct (or deconstruct) a few yourself. But you probably haven’t seen a lot of examples of effective recursion in the wild. In fact, other than the exotic nature of this approach, you may not have considered when and where recursion is useful, or how dangerous it can be if used carelessly.

What is Recursion Good For?

Recursion is a technique for iterating over an operation by having a function call itself repeatedly until it arrives at a result. Most loops can be rewritten in a recursive style, and in some functional languages this approach to looping is the default.

However, while JavaScript’s functional coding style does support recursive functions, we need to be aware that most JavaScript compilers are not currently optimized to support them safely.

Recursion is best applied when you need to call the same function repeatedly with different parameters from within a loop. While it can be used in many situations, it is most effective for solving problems involving iterative branching, such as fractal math, sorting, or traversing the nodes of complex or non-linear data structures.

One reason that recursion is favored in functional programming languages is that it allows for the construction of code that doesn’t require setting and maintaining state with local variables. Recursive functions are also naturally easy to test because they are easy to write in a pure manner, with a specific and consistent return value for any given input, and no side effects on external variable states.

Looping

The classic example of a function where recursion can be applied is the factorial. This is a function that returns the value of multiplying a number again and again by each preceding integer, all the way down to one.

For example, the factorial of three is:

3 × 2 × 1 = 6

The factorial of six is:

6 × 5 × 4 × 3 × 2 × 1 = 720

You can see how quickly these results get big. You can also see that we’re repeating the same behavior over and over. We take the result of one multiplication operation and multiply it again by one less than the second value. Then we do that again and again until we reach one.

Using a for loop, it’s not difficult to create a function that will perform this operation iteratively until it returns the correct result:

var factor = function(number) {
  var result = 1;
  var count;
  for (count = number; count > 1; count--) {
    result *= count;
  }
  return result;
};
console.log(factor(6));
// 720

This works, but it isn’t very elegant from a functional programming perspective. We have to use a couple of local variables that maintain and track state in order to support that for loop and then return a result. Wouldn’t it be cleaner if we could ditch that for loop, and take a more functional JavaScript approach?

Recursion

We know JavaScript will let us write functions that take functions as arguments. So what if we want to use the actual function we’re writing and execute it in the context of running it.

Is that even possible? You bet it is! For example, take the case of a simple while loop like this:

var counter = 10;
while(counter > 0) {
    console.log(counter--);
}

When this is done, the value of counter has been changed, but the loop has done its job of printing out each value it held as we slowly sucked the state out of it.

A recursive version of the same loop might look more like this:

var countdown = function(value) {
    if (value > 0) {
        console.log(value);
        return countdown(value - 1);
    } else {
        return value;
    }
};
countdown(10);

Do you see how we’re calling the countdown function right inside the definition of the countdown function? JavaScript handles that like a boss, and just does what you would hope. Every time countdown is executed, JavaScript keeps track of where it was called from, and then works backward through that stack of function calls until it’s finished. Our function has also avoided modifying the state of any variables, but has still taken advantage of a passed in value to control the recursion.

Getting back to our factorial case, we could rewrite our earlier function like this to use recursion:

var factorial = function(number) {
  if (number <= 0) { // terminal case
    return 1;
  } else { // block to execute
    return (number * factorial(number - 1));
  }
};
console.log(factorial(6));
// 720

Writing code this way allows us to describe the whole process in a stateless way with no side effects. Also worth noticing is the way we test the value of the argument being passed in to the function first thing, before doing any calculations. We want any functions that are going to call themselves to exit quickly and cleanly when they get to their terminal case. For a factorial calculated this way, the terminal case comes when the number passed in is zero or negative (we could also test for negative values and return a different message, if we so desired).

Tail Call Optimization

One problem with contemporary implementations of JavaScript is that they don’t have a standard way to prevent recursive functions from stacking up on themselves indefinitely, and eating away at memory until they exceed the capacity of the engine. JavaScript recursive functions need to keep track of where they were called from each time, so they can resume at the correct point.

In many functional languages, such as Haskell and Scheme, this is managed using a technique called tail call optimization. With tail call optimization, each successive cycle in a recursive function would take place immediately, instead of stacking up in memory.

Theoretically, tail call optimization is part of the standard for ECMAScript 6, currently the next version of JavaScript, however it has yet to be fully implemented by most platforms.

Trampoline Functions

There are ways to force JavaScript to perform recursive functions in a safe manner when necessary. For example, it’s possible to construct a custom trampoline function to manage recursive execution iteratively, keeping only one operation on the stack at a time. Trampoline functions used this way can take advantage of JavaScript’s ability to bind a function to a specific context, so as to bounce a recursive function up against itself, building up results one at a time until the cycle is complete. This will avoid creating a deep stack of operations waiting to be performed.

In practice, making use of trampoline functions usually slows down performance in favor of safety. Additionally, much of the elegance and readability we obtain by writing our functions in a recursive manner gets lost in the code convolutions necessary to make this approach work in JavaScript.

If you’re curious, I encourage you to read more about this concept, and share your thoughts in the discussion below. You might start with a short thread on StackOverflow, then explore some essays by Don Taylor and Mark McDonnell that dig deeper into the ups and downs of trampolines in JavaScript.

We’re Not There Yet

Recursion is a powerful technique that’s worth knowing about. In many cases, recursion is the most direct way to solve a complex problem. But until ECMAScript 6 is implemented everywhere we need it with tail call optimization, we will need to be very careful about how and where we apply recursion.

Frequently Asked Questions (FAQs) about Recursion in Functional JavaScript

What is the Base Case in Recursion and Why is it Important?

The base case in recursion is the condition that stops the function from calling itself indefinitely. It’s crucial because without it, the recursive function would keep calling itself infinitely, leading to a stack overflow error. The base case is typically a condition that the function checks before making a recursive call. If the condition is met, the function returns a value and stops calling itself.

How Does Recursion Work in JavaScript?

In JavaScript, recursion works by a function calling itself until it reaches a base case. The function is divided into a base case and a recursive case. The base case returns a value without calling the function again, while the recursive case calls the function again with a different argument. The function continues to call itself until it reaches the base case, at which point it starts returning values.

What is Tail Recursion in JavaScript?

Tail recursion is a special kind of recursion where the recursive call is the last operation in the function. This is important because it allows JavaScript engines to optimize the recursion, using a technique called tail call optimization. This can significantly reduce the amount of memory used by the function, allowing it to handle larger inputs.

What are the Advantages and Disadvantages of Using Recursion in JavaScript?

Recursion can make code cleaner and easier to understand by breaking down complex problems into simpler ones. It’s particularly useful for tasks like traversing tree-like data structures. However, recursion can also be less efficient than iterative solutions and can lead to stack overflow errors if not implemented correctly.

How Can I Avoid Stack Overflow Errors in Recursive Functions?

Stack overflow errors occur when a recursive function calls itself too many times, filling up the call stack. To avoid this, ensure your recursive function has a base case that it will eventually reach. Also, consider using tail recursion, which can be optimized by JavaScript engines to use less memory.

How is Recursion Used in Functional Programming?

In functional programming, recursion is often used as a substitute for loops. Since functional programming discourages the use of mutable state, recursion can be used to perform repeated operations without changing any state.

Can All Recursive Functions be Converted to Iterative Ones?

Yes, theoretically, all recursive functions can be converted to iterative ones. However, the iterative version may be more complex and harder to understand, especially for functions that involve complex tree or graph traversals.

What is Mutual Recursion in JavaScript?

Mutual recursion occurs when two or more functions call each other in a circular manner. This can be a powerful technique for solving certain types of problems, but it can also be more difficult to understand and debug than simple recursion.

How Can I Debug a Recursive Function in JavaScript?

Debugging recursive functions can be challenging due to the repeated function calls. However, using console.log statements to print out the function’s arguments and return values at each step can be helpful. Also, using a debugger tool that allows you to step through the function calls can be very useful.

Are There Any Performance Considerations When Using Recursion?

Yes, recursive functions can be less efficient than their iterative counterparts due to the overhead of repeated function calls. They can also lead to stack overflow errors if they call themselves too many times. However, in many cases, the readability and simplicity of recursive solutions can outweigh these performance considerations.