What is tail recursion?7 min read

In many functional programming languages such as Haskell or Scala, tail recursion is an interesting feature in which a recursive function calls itself as the last action. For example, we have a recursive function that calculates the greatest common divisor of two numbers in Scala:

def gcd(a: Int, b: Int): Int = {
    if (b == 0) a else gcd(b, a % b)
}

Compliers usually execute recursive procedures by using a stack, which is a LIFO (last-in-first-out) data structure. The information for the most recent recursive call, including their parameter values, is at the top of the stack; the initial recursive call lies at the bottom. When performing a recursive call, the information of this procedure is said to be pushed on the stack; upon the termination, its information is poped.

Recursive functions are, in most cases, far less efficient than an equivalent function written using explicit iteration. This is because each recursive call requires a “stack space”, which is limited in most languages and often leads to “stack overflow” errors. However, it’s not the case if the function is tail-recursive and written languages with some degree of “tail call optimization” such as Haskell or Scala.

Let’s evaluate the value of gcd(14, 21) to find out what I mean:

gcd(14, 21)
if (21==0) 14 else gcd(21,14%21)
if (false) 14 else gcd(21,14)

gcd(21,14)
if (14==0) 21 else gcd(14,21%14)
if (false) 21 else gcd(14,7)

gcd(14,7)
if(7==0) 14 else gcd(7,14%7)
if(false) 14 else gcd(7,7)

gcd(7,7)
if(7==0) 7 else gcd(7,7%7)
if(false) 7 else gcd(7,0)

gcd(7,0)
if(0 == 0) 7 else gcd(0,7%0)
if(true) 7 else gcd(0,7%0)
7

From our observation, we can notice recursive calls to gcd go from one call to the next, and it eventually terminates. In between, we have expressions that are different from a simple recursive call like if then else expression but we always get back the shape of gcd and there is no extra computation.

This recursive function is an example of tail recursion because the gcd function always calls itself as the last action, and you can reuse the stack frame because of this fact. Once upon termination, the previously pushed recursive call is popped, and this stack space is replaced by a new (if any) recursive call being pushed. For example, the first call to gcd(14,21), the information of this procedure is pushed to the stack, after computing the else part of this function, which gives us another recursive call gcd(21,14), for this moment, the call to gcd(14,21) has terminated due to there is nothing to do with this anymore, its information is popped and then the call to gcd(21,14) replace its place. So on and so forth, with subsequent recursive calls.

Hence, the tail-recursive function can execute in constant stack space and it’s just efficient as an equivalent iterative process. Here is our tantamount iterative version to compute gcd:

def gcdIterative(a:Int, b:Int): Int = {
    var max = Math.max(a, b)
    var min = Math.min(a, b)

    while (min != 0) {
      val tempRs = max % min
      max = min
      min = tempRs
    }
    max
}

Non tail-recursive example

Non-tail-recursive functions are those functions in which the recursive call is not the last part of the function (as there is more work to be done). For example, to compute the factorial of a number by using recursion:

def factorial(n:Int):Int = {
    if (n == 0) 1 else n * factorial(n - 1)
}

Let’s evaluate factorial(5):

factorial(5)
if (5 == 0) 1 else 5 * factorial(5 - 1)
5 * factorial(4)
5 * (4 * factorial(3))
5 * (4 * (3 * factorial(2))
5 * (4 * (3 * (2 * factorial(1)))
5 * (4 * (3 * (2 * (1 * factorial(0))))
5 * (4 * (3 * (2 * (1 * 1))))
120

For each recursive call, our expression becomes constantly bigger and bigger until reduce the final result. The crux here is our recursive call is not the last action to be performed, after calling factorial(n - 1), there are still more work to be done, that is we had to multiple the result of this recursive call to n. This is not a tail-recursive function as a lot of space overhead required to store the immediate results on each recursive call that we all need to keep until reaching the final value.

Tail call optimization

In imperative languages such as Java or C, we use loops to repeat a block of code over and over again or to modify the program state, along the way, we increment or decrement the counter and the loop terminates until it reaches the termination, the state of the program can be modified all the time. In functional languages, even you can still program iteratively but it’s strictly discouraged since function programs don’t have a mutable state. Because of this, recursion is the only feasible way to repeat a block of code, and perhaps all of them support “tail call optimization”, otherwise, they would be useless.

I have alluded to “tail call optimization” for quite a bit. So, what it’s about? Tail call optimization is a feature in functional languages in which you make a call to a recursive function, and it takes no additional space, the only situation that happens when the recursive procedure is the last action (i.e, tail recursion). Generally speaking, if there is a function f calls function g as the last action, then space required for f is now used by g, and no extra space was created.

So, for example, in our gcd example, it’s a tail-recursive function after the stack frame is allocated to the first call gcd(14,21), as the last action is again to call the value of gcd(21,14), here the compiler smart enough to figure out not to allocate the information of gcd(21,14) to a new stack frame, the tail call gcd(14,21) is popped out from the stack, and this stack frame now has the information of gcd(21,14), hence, constant stack space for the recursive call is preserved.

In some languages that do not support tail recursion, the space needed for computing gcd as in our example will never be constant; in fact, this will cost us O(n) space.

Tail-recursive function in Scala

In Scala, direct calls to the current function are optimized, however, an indirect call to the current recursive function is not optimized by default. We use @tailrec annotation to explicitly say that is a tail-recursive function, please optimize it, here is an example of tail recursion on calculating factorial:

def factorial(n: Int): Int = {
      @tailrec
      def iterator(accumulator: Int, x: Int): Int = {
        if (x == 0) accumulator
        else iterator(accumulator * x, x - 1)
      }
      iterator(1, n)
}

factorial(5) // 120

Here we simply rewrite our non-tail-recursive factorial function to a tail-recursive one by introducing a nested tail-recursive function inside the factorial function, this nested function takes 2 parameters, accumulator is for current accuminated value and x has the same value as n. We enforce the compiler to optimize this iterator function by placing @tailrec annotation above it.

Let’s evaluate the factorial(5) and see iterator is indeed a tail-recursive function:

factorial(5)

iterator(1, 5)
if (5 == 0) 1 else iterator(1 * 5, 5-1)
if (false) 1 else iterator(5, 4)

iterator(5,4)
if (4 == 0) 5 else iterator(5 * 4, 4-1)
if (false) 5 else iterator(20, 3)

iterator(20, 3)
if (3 == 0) 20 else iterator(20 * 3, 3-1)
if (false) 20 else iterator(60, 2)

iterator(60,2)
if(2==0) 60 else iterator(60 * 2, 2 - 1)
if(false) 60 else iterator(120, 1)

iterator(120,1)
if(1==0) 120 else iterator(120 * 1, 1-1)
if(false) 120 else iterator(120, 0)

iterator(120,0)
120

In most of our examples, the recursive function directly calls itself, gcd, factorial, or iterator. Yet keep in mind that they are still tail-recursive functions no matter how they are being called (indirect or direct) if the call to the recursive call is the last action.

In case you put the @tailrec annotation in front of a non-tail recursive function, the compiler simply wouldn’t compile:

@tailrec
def fibonacci(n:Int):Int = {
     if (n < 2) n else fibonacci(n - 1) + fibonacci(n - 2)
}

In this function, after calling fibonacci(n-1) and fibonacci(n-2), there is still an “extra step” in which you must add them together. Thus, it’s not tail recursive.

Wrapping up

In conclusion, the tail call is a feature in programming languages that support tail call optimization. A function is a tail-recursive when the recursive call is performed as the last action and this function is efficient as the same function using an iterative process. Compilers allocate memory for recursive function on stack, and the space required for tail-recursive is always constant, as in languages such as Haskell or Scala. However, in a language where tail call optimization is not one of its parts, tail-recursive is simply not standout. In Scala, you can enforce the compiler that a function is tail-recursive by @tailrec annotation.