Iteration versus Recursion in JavaScript
A behind-the-scenes look at the differences and how to make the right decision of which to use
Iteration
One of the most essential tools in control flow is the use of iterative statements. These iterative statements typically come in the form of a:
- for statement
- for in statement
- for of statement
- while statement
- do…while statement
In these iterative statements, “label statement”, “continue statement”, and “break statement” can be used in conjunction to give further control of the loop behavior.
Besides the above mentioned iterative statements, there are also iterative array methods, such as:
- forEach
- map
- filter
- reduce
What separates these from the previously mentioned, is that these iterative array methods require a callback function. This is the fundamental difference in how these iterative array methods operate as compared to the traditional iterative statements above as we will see when we take a look behind the scenes.
Recursion
Now that we’ve learned what an iteration is, let’s take a look at recursions and how they differ.
Recursions describe the behavior of recursive functions, which is to invoke or call itself. A basic comparison of iteration and recursion use for calculating factorial is shown below:
Side Note: Tail Call Optimization (TCO) is an optimization carried out by the compiler or engine that allows the “loop” to continue without growing the stack. Even though ES6 came out with TCO as a part of its new standard, all the major browsers have had a bumpy ride implementing it and as of now, it’s been in limbo. That being said, it’s good to keep in mind how to convert one for TCO. Take a look here for more details regarding its implementation history for JavaScript.
When recursiveFactorial is called, the following takes place:
As we can see, besides the initial call to recursiveFactorial, it in itself is called an additional four times, and after reaching the base case of n=== 1, it backtracks all the way, fulfilling each subsequent computation to reach 120.
Before looking behind the code, let’s concretely define the components of a recursive function. There are two essential components that make a recursive function desirably functional: the recursion and the base case.
The recursion is the part where the function is called, which in our factorial example would be recursiveFactorial(n-1). Take note, that the function can be called in multiple places in itself, as well as multiple times in the same expression with likely different arguments. That is technically enough to make a function recursive, but it would be undesirable as it would crash with a stack overflow error.
The base case is where we define the stopping condition. In our factorial example, the base case is if (n===1). Take note that there can be as many base cases as the algorithm requires.
Going Behind-the-Scenes
First, we need to understand that JavaScript is a single-threaded concurrent programming language. This means that JavaScript does one thing at a time (JavaScript Runtime) and through a cooperative relationship with the Web APIs, callback queue, and event loop allows “multi-tasking” in the form of scheduling.
Below shows the different components of JavaScript in action:
The JavaScript Runtime or the JavaScript engine (V8 for Chrome, SpiderMonkey for FireFox) contains the Heap and Call Stack. The Heap is an unstructured area of memory where memory allocation occurs for all the variables and objects. The Call Stack is a data structure that follows the Last-In-First-Out (LIFO) system and keeps track of the function calls in stack frames (denoted by the yellow rectangles in the figure above) which contain the function along with its arguments and local variables.
Web APIs are a part of the browser and contains the essential APIs that allows JavaScript to function in a concurrent manner. Examples include DOM events, such as the click and scroll event, AJAX requests, and the setTimeOut function.
The Callback Queue is a data structure that follows the First-In-First-Out (FIFO) system and queues the functions resolved by the Web APIs.
The Event Loop’s purpose is to add one queue item from the Callback Queue to the Call Stack when the Call Stack is empty.
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Can you see how the Call Stack would change with the recursiveFactorial example?:
With a more complete picture under our belt, let’s circle back to iteration and recursion.
In iteration, the looping relies on itself. Little to no change occurs to the Call Stack. In recursion, however, the looping relies on repeatedly calling on itself, which consequently adds a stack frame to the Call Stack for each function call. This also means a great deal of removing and adding takes place, which in turn adds a significant burden in run time for increasing number of calls. When the data set or input is small, the difference between iteration and recursion in terms of time is insignificant, otherwise, iteration often performs better.
In the scenario of a significantly large loop or even an infinite loop in iteration, the browser tab will seem unresponsive to any action taken by the user on the page. This is because the loop taking place in the Call Stack is blocking any item coming from the Callback Queue. That being said, other tabs would work normally since only the process for that one tab is stalled.
In a similar case where a large enough recursion occurs, JavaScript actually crashes due to stack overflow. Each browser has a stack limit which if exceeded would lead to the stack overflow error.
Typically, iteration can be converted to recursion and vice versa. So aside from performance, there is also readability and maintainability to be concerned about when choosing which approach to use. Recursion, due to its algorithmic nature often tends to require a fewer number of lines of code. Also, certain algorithms are more easily understood and intuitive to program through recursion than iteration. In the end, it all depends on the scope of the project, the allocated resources, the platform, and the audience size, among other factors, when choosing the tools and techniques to use.
