Tail recursion (or tail recursion?) is a specific type of recursion. In particular, a recursive function is said to use tail recursion if the call to itself occurs as the last action of the function.

To understand a little better, let's say we want to write a recursive function def sum(n: Int): Long, that if we pass the parameter n = 5, then the result is the following sum: 5 + 4 + 3 + 2 + 1 = 15.

Let's compare 2 different ways to implement this algorithm, in the first case using a normal recursive function , and in the second using tail recursion .

1. Normal recursive function

def sum(n: Int): Long =
    if (n <= 0)
        0
    else
        n + sum(n - 1)

In this case, the function does not use tail recursion because although the recursive call sum(n - 1)appears at the end of the function, it is not actually the last action. Actually, to complete that statement, you have to execute first, sum(n - 1)and then the additional step of adding the result to is required n.

2. Recursive function with tail recursion

def sum(n: Int, total: Long = 0): Long =
    if (n <= 0)
        total
    else
        sum(n - 1, total + n)

Although this function produces identical results to the previous function, this one can be said to use tail recursion because the recursive sum(n - 1, total + n)call is the last action of the function.

What does it matter if the recursive function uses "tail recursion" or not?

When a recursive function calls itself several times, the calls accumulate on the call stack, which in itself is not very efficient because it consumes memory. But even worse, if too many calls accumulate on this stack, it will eventually overflow the call stack and throw you the exception java.lang.StackOverflowError.

We can observe this if we execute the normal recursive function with a nvery high value:

println(sum(1000000))

Normal recursive function demo

Result:

java.lang.StackOverflowError
  at Rextester$.sum(source.scala:12)
  at Rextester$.sum(source.scala:12)
  at Rextester$.sum(source.scala:12)
  ...

This inefficiency is a serious problem for a functional language like Scala that promotes the use of recursive functions.

However, when Scala detects that the recursive function uses tail recursion , then the compiler is able to perform an optimization on the code automatically, effectively removing the recursion entirely and replacing it with a simple loop. This optimization is commonly known as tail call optimization .

Using Java syntax for a moment, it is as if the compiler transforms the recursive function with tail recursion to the following code without recursion (more or less):

long sum(int n) {
    long total = 0;
    while(true) {
        if (n <= 0) {
            return total;
        } else {
            total += n;
            n -= 1;
        }
    }
}

Due to this automatic transformation, memory usage remains constant regardless of the value assigned to n, and the risk of call stack overflow ( StackOverflowError) is completely avoided:

println(sum(1000000))

Recursive function demo with tail recursion

Result:

500000500000

conclusion

Due to the automatic optimization that Scala applies to recursive functions with tail recursion , it is worth trying to tune the algorithm of a recursive function, when possible, to use tail recursion . In particular, it is important to do this if the function makes several recursive calls, to avoid consuming too much memory, or even overflowing the call stack.

Note that many other programming languages, including Java, do not include this automatic optimization. But since Scala is a functional language that promotes liberal use of recursive functions, it makes sense for your compiler to include this optimization to minimize its impact on performance and memory.

Additionally, even if we use another programming language that does not include this automatic optimization, it is good to be aware of what tail recursion is . Because there will be times where it will be necessary to optimize a recursive function manually to correct memory problems or call stack overflow. In those cases, the key is to find a way to redesign the function's logic to use tail recursion . If this can be achieved, then it is trivial to manually convert the logic to use a loop instead of recursion.

Edit - using the @tailrec annotation to ensure the use of "tail recursion"

Scala allows you to annotate recursive functions with the @tailrec( scala.annotation.tailrec) annotation. By adding this annotation, the compiler verifies that the recursive function is indeed using tail recursion and gives you an error if it isn't. This is a good way to confirm that the function will benefit from automatic optimization and that we have not made a mistake in the design of the function.

To see how this works, let's take the 2 recursive functions above again and add the annotation to both of them. First, the normal recursive function :

@tailrec def sum(n: Int): Long =
    if (n <= 0)
        0
    else
        n + sum(n - 1)

Demo of normal recursive function annotated with@tailrec

Result:

Error(s), warning(s):
source_file.scala:13: error: could not optimize @tailrec annotated method sum: it contains a recursive call not in tail position
            n + sum(n - 1)
              ^
one error found

As we can see, the compiler is warning us that the function does not use tail recursion .

But if we now apply the annotation to the recursive function that does use tail recursion :

@tailrec def sum(n: Int, total: Long = 0): Long =
    if (n <= 0)
        total
    else
        sum(n - 1, total + n)

Recursive function demo with tail recursion annotated with@tailrec

Result:

500000500000

In this case, the compiler returns no error, confirming that the function does indeed use tail recursion and that it will benefit from the compiler's automatic optimization.

It's already well answered by @sstan, so I'm not going to delve too deep into what end-of-tail recursion optimization is . Just comment that it is neither better nor worse than what you call normal recursion . It has its advantages for some cases, but it's better for the compiler to choose the best way to implement recursion.

Calling a function creates a new environment in which to execute the function's code. This environment is known as closure ( closure ) and is essential in any functional language. From an object-oriented programming point of view, you can also see the closure as an instance of the function and the function as if it were a class .

Every time a function is called, a closure is created, which will remain active until the function exits. Thanks to this closure, the function can call other functions and continue where it was just by replacing the called function with the returned value (This is known as "Referential Transparency" ). Likewise, thanks to the fact that a closure maintains its execution state, it is possible to intercept the errors produced in the function that we have called and thus try to correct them.

In the case of functions that call themselves (aka "recursive call"), each call creates closures almost identical to the previous one. If we are sure that this call is at the end of the queue of calls, or what is the same, if we can replace the call stack with the return value without the need to do more operations, it would be possible to use a single closure for all calls of the function. In this way we would save resources by not having to generate all the closures, although in exchange we would lose the possibility of trapping errors and the advantage of having "lazy evaluations" .

The "lazy evaluation" thing is worth commenting on. An evaluation is said to be lazy if only the values ​​that are strictly necessary to obtain the result are computed. One of the characteristics of functional programming is precisely to be able to defer the calculation as much as possible until the end of the sequence of operations and thus discard operations that are not going to influence the final result.

The current state of the compilers (in functional programming) already allows us to infer what operations are not necessary to perform or what kind of optimizations improve execution (tailrec opt, inline call, etc). In general, the compiler will create the best version following the help we can give it.

For example, we can give the following definition of the Fibonacci function:

def fib(n: Int): BigInt = n match {
  case 0 => 1
  case 1 => 1
  case _ => fib(n-1) + fib(n-2)
}

This definition would not be tailrec . We can create a version that is:

@tailrec 
def fib(n: Int, v: BigInt=0, acc: BigInt=1): BigInt =
  if (n == 0)
    acc
  else
    fib(n-1, acc, acc+v)

This tailrec version will have no memory problems and will probably be much faster than the previous version. Still not the best version. To give ideas, you could save the intermediate results so you don't always have to calculate them, at the cost of spending a little more memory (aka "memoization" ).

But let's see this other lazy version:

val fib: Stream[BigInt] =
  BigInt(1) #:: BigInt(1) #:: (fib zip fib.tail) map {case (a,b) => a+b}

We are defining fibin terms of itself, which gives an infinite sequence. The peculiarity of using Streams is that its expansion is carried out as we discover new elements ( lazy evaluation ), storing the elements as they are calculated. It is an easy way to calculate the fibonacci sequence and more efficient than the previous tailrec version .

I hope I have clarified something for you.