Recursion vs Generators: Which One is Better for Splitting Problems in JavaScript?

Posted by     4 Minutes read

One of the day to day trade-offs that we are forced to make when writing code, is balancing between performance, efficiency and readability.

For example, writing object-oriented code may be good for readability, but at the same time it may reduce our ability to minify the code and reduce code size.

One of the ways to improve code readability and maintainability, is to split it into small chunks that are easy to understand.

This can be done by splitting the code into small functions with meaningful names, and modularization of the code.

Often we encounter problems that can be solved by recursion – assuming that the solution already exists for part of the problem and proceeding from there. This approach often results in shorter and more readable code.

However, it has its drawbacks, especially when there are many stages – it is not memory efficient, and it creates a stack of function calls that blocks the main thread and can lead to stack overflow.

In this blog post I will review this approach, and suggest a different way to handle similar problems using generators.

Recursion: Breaking Down Problems into Smaller Sub-Problems

Recursion is a term that originates from the field of Mathematics.

It comes from the Latin verb recurro, that means to run back.

The meaning is to define a problem in the terms of itself – for example, if you would like to calculate the nth fibonacci number, it is easy to describe it as the sum of the n-1 fibonacci number and the n-2 fibonacci number.

In the following example I’m using memoization in order to cache the calculation result and make the code more efficient.

This approach has several advantages:

  • Recursion can make code more readable and elegant, as it allows for a more natural expression of the problem solution.
  • Recursive algorithms can be simpler and shorter than their iterative counterparts.
  • Some problems are naturally recursive, and can be more easily expressed using recursion.
  • Recursive functions are good for solving problems that have a recursive structure, like tree traversal and graph traversal.

However, it also has significant drawbacks:

  • Recursive functions can be harder to debug and understand than iterative functions.
  • Recursive functions can cause a stack overflow if the recursion goes too deep (the example above does).

TCO, or rather, Tail Call Elimination in JavaScript is an optimization that would enable developers to use recursion without causing stack overflow – as long as the function only calls itself from the return statement, and all of the information that is needed with it.

This optimization was originally part of ES2015, but unfortunately it was abandoned and currently it is only supported by Safari.

Also, recursion isn’t a good fit for every problem – some are more efficiently solved using iteration.

Generators: Splitting Problems with Improved Page Performance

Generators, AKA ES6 generators, are another technique that allows you to solve a problem by breaking it down into smaller sub-problems, but they offer some advantages over recursion.

They are a type of function that can be paused and resumed multiple times.

They allow you to create iterator objects, which can be used to loop over a set of data or a sequence of operations, without the need to load all the data into memory at once.

A generator function is defined using the function* syntax, and inside the function, the yield keyword is used to pause the function and return a value.

Each time the generator’s next() method is called, the function resumes from where it left off and continues to execute until it encounters another yield statement or the end of the function.

Generators are commonly used for creating iterators, working with asynchronous code and implementing features like lazy evaluation. They also provide a way to create infinite sequences, which can be useful in some cases.

They are supported by the latest versions of all common browsers except IE and Opera Mini. For general support, use regenerator-runtime npm package (1.7kb).

Here is an implementation of the fibonacci number calculator using a generator:

This example does not cause stack overflow, however, it does cause a long task:

In the following example I use scheduler.postTask to yield into the main thread and avoid long tasks:

This code does not cause stack overflow, and if we create a recording in Chrome’s performance tab, we can see that there are no long tasks:

The scheduler API is not yet supported by Firefox and Safari. You can use scheduler-polyfill (62.4kb unpacked), or simply setTimeout(0).

This approach completely removes the limit on the maximum number of steps in the calculation, and opens exciting new possibilities. For example, we can have a function that prints all of the fibonacci numbers without any exit condition.

When running the following code, the page continues to be responsive, and the only limitation is that at some point the returned value settles on “Infinity”.

Conclusion

JavaScript generators offer a powerful technique to solve recursive problems.

They are more efficient and can be used to implement lazy evaluation.

While for small problems with few stages recursion provides a solution that requires less code to be written, for larger problems I encourage you to consider generators.

References

I’d like to express my gratitude to David Hakak, Noam Rosenthal, John Reilley and Jamie McCrindle for proofreading my post and providing useful suggestions.

I got help from Chat GPT with the structure and editing of this blog post.

Originally Published:

Create Your Content Campaign Today!

Start now