What Is Recursion?
A recursive function is a function that invokes itself. This process of self-invoking is called recursion.
So that a recursive function will not invoke itself infinitely, it must include an exit condition.
This bit of code demonstrates how recursion works in simple terms, counting down from five to one:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
function countDown(num) { if (num === 0) { console.log('All done!'); return; } console.log(num); countDown(num - 1); } countDown(5); // 5 // 4 // 3 // 2 // 1 // All done! |
This function recursively calls itself, passing one lower number than the previous, until the number is zero (the exit condition), at which point it exits.
A more useful example is a recursive function that calculates the factorial of a number:
1 2 3 4 5 6 7 8 9 10 11 |
function factorial(n) { if (n === 0) { return 1; } else { return n * factorial(n - 1); } } console.log(factorial(7)); // 5040 |
We can reduce this to a single line with the use of an arrow function and a ternary expression:
1 2 3 |
const factorial = n => n === 0 ? 1 : n * factorial(n - 1); |
Issues with Recursion
The biggest issue with recursive function calls is that they don’t scale well. Each call adds another stack frame (a block of memory containing a set of instructions, basically) to the call stack, and each stack frame resides in its own memory location. Once the exit condition is encountered, all of the frames on the stack get resolved and removed.
So, at the point that the exit condition is encountered, the number of frames on the stack is equal to the total number of recursive calls made. If that number is large, that can amount to a very large number of stack frames, and hence a great deal of memory allocated.
For example, this recursive function calculates Fibonacci numbers:
1 2 3 4 5 6 |
function fibonacci(num) { if (num <= 1) return num; return fibonacci(num - 1) + fibonacci(num - 2); } |
This function calculates the n
th number in the Fibonacci sequence, where n
is the number passed to the num
parameter. It works quite well for numbers up to about 40. But fibonacci(45)
takes about 30 seconds to calculate, and fibonacci(50)
takes about 15 minutes. So the number of frames on the call stack increases exponentially as the sequence number increases arithmetically.
On the other hand, it is possible to calculate large Fibonacci numbers using a while
loop with no appreciable degradation in performance:
1 2 3 4 5 6 7 8 9 |
function fibonacci(num) { let [a, b] = [0, 1]; for (let i = 1; i < num; i++) { [a, b] = [b, a + b]; } return b; } |
Using this method, a call to fibonacci(50)
immediately returns 12586269025
.
Most recursive functions can also be written using iterative loops. Because they often perform much more quickly, many programmers recommend iterative loops exclusively over recursive calls. However, recursive procedures can often be made to perform just as well as iterative loops by implementing tail call optimization.
Tail-Call Optimization
A tail call is a function call that:
- Happens on the last line of a function.
- Is the only thing that happens on the last line of the function.
If a function call is a tail call, it can be optimized. This optimization is called tail call optimization, or TCO. TCO is implemented by most languages and platforms.
TCO can significantly improve the performance of recursive functions. The optimization allows the reuse of the existing stack frame, rather than requiring the allocation of a new one, for each recursive call. Since, by definition, the tail call is the last instruction in the frame, jumping to the top of the frame and repeating it doesn’t have unpredictable results, as it would if there were instructions following the call.
In standard recursion, when a frame encounters the ending condition, it returns its return value to its caller and the frame is released. This continues until the final return value is sent to the original caller of the recursive function.
In tail-call recursion, once the function calls itself, the same frame is reused with whatever new argument values are in the recursive call. As such, from an execution standpoint, a tail-call recursion is much like a while
loop.
Here’s a fibonacci implementation using tail-call recursion. In this example, the input (num
) functions as a counter and gets decremented with each call, and a
and b
keep accumulating the fibonacci sequence as we go.
1 2 3 4 5 6 |
function fibonacci(num, a = 0, b = 1) { if (num === 1) return b; return fibonacci(num - 1, b, a + b); } |
The critical difference in this version is that we aren’t adding the results of two recursive calls together on the final line as the first example does. That counts as doing something other than just making the call on the last line, so tail call optimization can’t be applied.
A Little Benchmarking
Suppose we set both of these up to increment a count variable in each call and return the result. Here’s the first example, modified to return a count:
1 2 3 4 5 6 |
function fibonacci(num, count = 0) { if (num <= 1) return count; return fibonacci(num - 1, ++count) + fibonacci(num - 2, ++count); } |
And here’s the tail call version, also modified to return a count:
1 2 3 4 5 6 |
function fibonacci(num, a = 0, b = 1, count = 0) { if (num === 1) return count; return fibonacci(num - 1, b, a + b, ++count); } |
Suppose we then call fibonacci(40)
(the 40th fibonacci number is 102,334,155) with each version. The tail call version returns 39
(it’s always one less than the input value), while the “ordinary” version returns 2837341129
! That takes a few seconds, and it uses enough memory to raise concerns about exceeding RAM capacity. It gets exponentially worse as you go higher.
So, it’s important to keep in mind that recursive calls often scale very poorly. Tail call optimization can often have a dramatic impact on performance. In this case, it turns an exponential operation into an arithmetical one.
It’s also important to keep in mind that not every platform and/or language supports TCO. Python doesn’t; Python’s creator makes the point that since it messes up the stack trace it makes things hard to debug.
For more information about which languages implement TCO, see this Wikipedia article.
Also, I’ve seen articles that are not very old that say that, while the ES6 spec mandates TCO, Safari is the only browser that supports it. I’ve tested these in node, Chrome and Firefox, and they all support it at present. But it’s something to keep in mind if you’re relying on TCO.
To Sum Up …
Recursion isn’t just a rather tricky technique that hiring managers use to test candidates’ coding skills. It has real-life applications too. For example, the “flood fill” (paint bucket) tool in paint programs fills contiguous pixels of the same color as the one clicked with a new color. This lends itself well to recursion. Googling “flood fill recursion javascript” will yield numerous articles and videos about it, including this one.
If you are considering a recursive solution to a problem, tail call recursion is an important idea to keep in mind. The difference between an “ordinary” recursion implementation and a tail call recursion implementation can be quite dramatic. So much so, in fact, that it is often the difference between a practical solution and an impractical one.