Scala has some advanced features compared to other languages including support for tail recursion. But let’s first look at what it means and why it helps in building recursive algorithms.
An overview of tail recursion
Tail recursion is a subroutine (function, method) where the last statement is being executed recursively. Simply saying, the last statement in a function calls itself multiple times.
These functions are more performant as they take advantage of tail call optimisation. They simply keep calling a function (the function itself) instead of adding a new stack-frame in memory.
It comes very handy in some situations, usually when computing the result requires an iterative algorithm. Of course, using some kind of loop mechanism, like a for or while loop, could be a solution, however loops require us to maintain variables outside the loop to keep track of the state of our iteration.
Tail recursive functions should pass the state of the current iteration through their arguments.
They are immutable (they are passing values as argument, not re-assigning values to the same variables) and more readable.
Tail call optimisation in Scala
Scala supports tail recursive functions by performing tail call optimisation. It also has a special annotation, @tailrec, to ensure that the method can be executed in a tail recursive manner, otherwise the compiler produces error.
What are the requirements to write a tail recursive function?
- There has to be an exit condition: without this the function would end up in a never ending loop which is certainly not the goal with any iterative computation. An exit condition can be achieved by using a condition and when the condition is met the function returns a value, otherwise it keeps calling itself with a different set of attribute values.
- A tail recursive function has to be able to call itself: this might not happen if the exit condition is met in the first iteration, however all arguments have to be passed to the function itself for any subsequent calls.
Here’s a sample of a tail-recursive function in Scala:
As you can see in the snippet this tail-recursive function will return the number of steps needed until we reach (or go beyond) the defined distance. It’s as simple as the example given. The only thing to remember is to define the return type of our tail-recursive function as required by the Scala compiler.
