What is tail-call recursion?
A recursive function is any function that calls itself during its execution.
Recursive solutions to a problem can be more declarative than an iterative solution; making it easier to reason about. They are particularly useful when dealing with problems that can be broken down into smaller, easier-to-solve problems¹.
Let’s look at an example of a recursive function to get us going:
By looking at the example implementation you can see that the interpreter will have to keep all of the stack frames as it recurses until it hits its base case
!(n > 1). At this point it will start to unwind and use the returned values from the recursive calls in calculating the final result.
It’s not a big deal when you’re five levels deep but if you were dealing with larger numbers this would be a really great way to create a Stack Overflow.
Tail call recursion to the rescue
To get around this we need to find a way that the final recursive call can perform the final calculation without needing to unwind. To get this right we need to do two things:
- The recursive call must be the last thing the function does (i.e its result can’t be used as an input into the calculation as it is in the n! implementation above)
- We need to keep track of the current state of the calculation in one or more state variables such that the return value from the deepest recursive call is the final answer we’re looking for.
Looking at the example above, you can see that the current value of the calculation is being passed through in the
accumulator variable. This means that the final call to
implementation returns the answer we’re looking for and there is no need for the interpreter to keep references to the previous stack frames.
Now what I said above is only technically true if the runtime your code is executing in implements something called tail-call optimisation.
This is a feature that allows the runtime to recognise that it can discard the intermediate stack frames since the result to the final call can simply replace that entire set of frames.
The good news is that the ES6 language spec requires tail-call optimisation but the bad news is that very few implementations currently support this (only mobile and desktop Safari at the time of writing²). Given the lack of support in even ES6-compliant runtimes, it’s probably wise to keep any code that will receive extremely large inputs as iterative solutions until the implementations can catch up.