What is a recursive method?
A method that calls itself many times before reaching a specific condition or
base case.
What is a tail-recursive method?
A method which calls itself in the last instruction (
tail-call). In the case of Scala (and other FP languages), a
tail-recursive method can reuse the stack frames in each iteration.
We can specify that a method has to be tail-recursive using the annotation
@tailrec (if the implementation isn’t tail-recursive, the compiler shows an error).
In the following example, the tail-recursive method returns the last element of a list of Integers given by parameter:
If the given
list matches with a List of one element (
List(x)) the method responds with that element,
x.
In other case, if the
list matches with a List of many elements composed by a head
x and a tail
xs, the method calls itself passing the tail by parameter.
What is this strategy good for?
The depth of the JVM call stack is limited; for this reason, if we have deep recursive calls it’s a good idea to use a method tail-recursive to reuse stack frames and avoid stack overflow errors.
On the other hand, if we don’t have the case mentioned before, it’s better not to use a recursive tail method and leave the code more easy to read.
goto Part III
