Tail Recursion

One of the key enablers for implementing idiomatic, expressive and concise code in functional programming languages is the use of recursion in place of loops and mutable variables. However, recursion does come at a cost. Most runtime infrastructure dedicates a stack frame for each method call for managing local state. This means each recursive call can potentially own its own stack, causing performance issues as well as physical limits set by the number of bits available on the runtime infrastructure for addressing.

However, the Scala compiler rewrites recursive calls as a single stack loop, if the last call to be made in the recursive function is another function call, whether to itself or another call. Let us have a look at the example code below for calculating the nth number of a fibonacci series (1, 1, 2, 3, 5, 8, 13 ..)

scala> def fib(n: Int): Int = n match {
     |   case 0 => 1
     |   case 1 => 1
     |   case x => fib(x - 1) + fib(x - 2)
     | }
fib: (n: Int)Int

The code is pretty expressive, the 0th and 1st element of the series is 1 and all subsequent elements are the sum of previous two elements in the series. However, the call is not tail recursive, as the last instruction in the function is the addition operation and not a recursive call to itself.

Depending on the JVM parameters, the call fib(Int.MaxValue), will cause a stack overflow error. You can force the compiler to check whether a function is tail recursive by annotating the function with scala.annotation.tailrec.

Generally, non tail recursive calls can be made tail recursive by implementing an internal looping function, that uses accumulator and initial values as shown below,

scala> def fib(n: Int): Int = {
     |   @annotation.tailrec
     |   def loop(n: Int, previous: Int, current: Int): Int =
     |     if (n == 0) previous
     |     else loop(n - 1, current, previous + current)
     |   loop(n, 0, 1)
     | }
fib: (n: Int)Int

Of course, this is optimised for larger call depths, but obviously compromises on the brevity and expressiveness of code.