One Thing People Forget About Recursive Functions in JavaScript
“To understand recursion, one must first understand recursion” — Stephen Hawking
Recursion has many pitfalls. Most JavaScript developers don’t even think about using it until they encounter a specific problem. Recursive functions get little attention, especially in JavaScript because of some big performance limitations.
In this article, I’ll go over what recursive functions are, what the advantages are compared to classic iterations, and the one thing you may never forget when using recursive functions.
What are recursive functions?
If you already know this, feel free to skip to the next part. For anyone else, recursive functions are functions that call themselves. One of the classic examples for using recursion is generating the row Fibonacci (0, 1, 1, 2, 3, 5, …). Consider this function:
Do you see what’s happening here? The Fibonacci function is calling itself. For example, if we call fibonacci(3) our response will be 2. If we look at it visually, this is what happens:
Or if we look at it from the point of the call stack:
We call the function with argument value 3. The function will first call fibonacci(3–2), which will return an integer value of 1. The function returns and then the fibonacci(3–1) call will be executed which will in its turn need to call the fibonacci function 2 more times with arguments 0 and 1. Then the stack will eventually shrink until we’re back in our original function and the function call returns 2.
Although this is a very meager example, I hope you get the gist of what recursive functions represent. You’re probably thinking; this is nice and all, but what use it in the real world?
Real use-cases and advantages compared to classic iteration.
When I prepared my writing for this article I asked my developer friends if they had used much recursion in the past years. The response was clear. All of them had used it maybe once or twice and most just copied a script from StackOverflow.
So what examples are there of using recursion? Here’s a small list.
- Recursively looping through directories to perform CRUD operations on files and directories.
- Sort algorithms (Quicksort, …)
- Navigating through HTML and XML
- Collision detection in game development
- Breadcrumb generation in CMS systems
- Solving sudokus 😄
There are a lot of examples, and classically Functional Programmers will prefer recursion because it’s more declarative. Instead of looping and keeping the state explicitly somewhere in our code, the state is captured in the call stack. Recursion is very interesting if conditional decisions or back-tracking are necessary.
I’m not advocating that you should replace all your for loops by recursion. If a for loop gets too complex, it may be wise to try to encapsulate your logic in recursive functions, they might be easier to understand for the next person who has to read your code.
What you should never forget
When we call functions recursively, behind the screens, our call stack will grow. This is visible in the image above. What if we call the fibonacci function with integer value 100,000. How will it affect our application?
In JavaScript, the engine will step in if it thinks that the call stack grows too much and should be stopped. What you’ll see is that you’ll get something called a RangeError. Unlike some other languages, there is no hard limit. The engine will step in when it thinks that the memory usage runs out of control by the heavy growth of the call stack.
But what if you actually wanted to get the 100,000th value in the Fibonacci row, is it impossible to calculate it using recursive functions?
Tail calls
In comes, the tail calls. Tail calls are not something specific to JavaScript, they are a general technique for the optimization of recursive functions.
The idea is that if a function is called from the very last line of a recursive function, the calling function can be removed from the call stack.
For example, consider this function:
It will add all numbers from one to a particular number, so e.g. for 3 the result will be 3 + 2 + 1 = 6. In the call stack this will look like this:
When a programming language implement tail calls, what actually happens is this:
Instead of having to keep track of the calling functions. Tail call optimized languages will remove the calling functions from the call stack and ultimately just return the result from the last called function. This is only possible if the calling function has a return statement in which it only calls a function. If the function would have a return statement like return 1 + sumOneToNumber(x); it won’t be able to perform this optimization because the summation will have to be executed after the very last call.
This way we can prevent our call stack from growing out of control and preventing the RangeError.
Except.
JavaScript implements tail calls in a specific form called “Proper Tail Calls” (PTC). This, however, is only available since ES6, before ES6 there was no guarantee that the tail call optimization was going to be applied.
It is also important to note is that PTC only works if JavaScript is used in strict mode. Something worth reading about if you haven’t heard of ‘strict’ mode yet.
These limitations may be the reason that up until now we haven’t seen much recursion applied in JavaScript. It’s certainly worth discussing more as I believe that readability can greatly be enhanced with the use of recursive functions, a metric of the utmost importance in a good software project.
Conclusion
Recursion is a dangerous technique if applied with negligence. You may just run into a RangeError with some of your code deployed on production, something that didn’t happen during development because there wasn’t as much data in your test application.
In this blog, I’ve explained what a recursive function is. What exactly it does, where it can be applied in a real-world scenario, and what you have to pay attention to when using it.
I hope you learned something new and that this blog post will help make you better decisions in the future. Good luck!
More content at plainenglish.io
