Tail recursion

In the tail-recursive function, the recursive call is done as the very last activity. Because of this, it is possible to "finish" all the "preparations" for the call and then just "jump" back to the beginning of the function with new arguments. The Scala compiler rewrites tail-recursive calls as loops and hence such recursive invocations do not consume the stack at all. Usually, to make a recursive function tail-recursive, either some kind of state or some sort of and/or local helper function is introduced.

Let's rewrite our reverse function in the tail-recursive way:

def tailRecReverse(s: String): String = {
  def reverse(s: String, acc: String): String =
    if (s.length < 2) s + acc
    else reverse(s.tail, s.head + acc)
  reverse(s, "")
}

In this implementation, we've defined a local tail-recursive function, reverse, which shadows the argument s so that we do not unintentionally reference it, and also introduces an acc argument, which is needed to carry over the remaining part of the string. Now the reverse is called after the head of the string and acc are glued together. To return the result, we call the helper function with the original argument and an empty accumulator.

This implementation does not consume the stack, which we can check by throwing an exception in the base case and inspecting the stack trace:

scala> println(inspectReverse("Recursive function call"))
java.lang.Exception
  at $line19.$read$$iw$$iw$.reverse$1(<console>:3)
  at $line19.$read$$iw$$iw$.inspectReverse(<console>:5)

At the moment we're finishing the reversing of the string, we still have just a single recursive call in the stack. Sometimes it confuses the developer as it appears as if the recursive call would not be made. In this case, it is possible to disable tail-call optimization by using the notailcalls compiler option.

Sometimes the opposite is happening and a (presumably) tail-recursive call overflows the stack at runtime because the developer overlooked a recursive call in the head position. To eliminate the possibility for such kinds of error there is a special annotation for tail-recursive calls, @scala.annotation.tailrec:

def inspectReverse(s: String): String = {
  @scala.annotation.tailrec
  def reverse(s: String, acc: String): String = ...
}

The compiler will fail to compile head-recursive functions with this annotation:

scala> @scala.annotation.tailrec
     | def reverse(s: String): String = {
     | if (s.length < 2) s
     | else reverse(s.tail) + s.head
     | }
           else reverse(s.tail) + s.head
                                ^
On line 4: error: could not optimize @tailrec annotated method reverse: it contains a recursive call not in tail position

It seems as if we're on the safe side with properly annotated tail-recursive functions? Well, not 100%, because there is also a possibility that some functions cannot be made tail-recursive at all.

One of the examples, when tail recursion cannot be implemented, is mutual recursion. Two functions are mutually recursive if the first calls the second, and the second calls the first. 

One of the examples of such functions is Hofstadter Female and Male sequences, defined as follows:

def F(n:Int): Int = if (n == 0) 1 else n - M(F(n-1))
def M(n:Int): Int = if (n == 0) 0 else n - F(M(n-1))

Another example of a non-tail-recursive function is an Ackerman function (more about it can be found at https://en.wikipedia.org/wiki/Ackermann_function) with the following definition:

val A: (Long, Long) => Long = (m, n) =>
  if (m == 0) n + 1
  else if (n == 0) A(m - 1, 1)
  else A(m - 1, A(m, n - 1))

It is very simple, but not primitive recursive, it is stack-hungry, and it overflows the stack even with moderate values of m and n:

scala> A(4,2)
java.lang.StackOverflowError
  at .A(<console>:4)
  at .A(<console>:4)
...

There is a special technique called trampolining to implement non-tail-recursive functions on JVM.