Scala Tutorial

Recursive Function Application

Let’s compare the evaluation steps of the application of two recursive methods.

First, consider gcd, a method that computes the greatest common divisor of two numbers.

Here's an implementation of gcd using Euclid's algorithm.

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

gcd(14, 21) is evaluated as follows:

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

Now, consider factorial:

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

factorial(4) is evaluated as follows:

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

What are the differences between the two sequences?

One important difference is that in the case of gcd, we see that the reduction sequence essentially oscillates. It goes from one call to gcd to the next one, and eventually it terminates. In between we have expressions that are different from a simple call like if then else's but we always come back to this shape of the call of gcd. If we look at factorial, on the other hand we see that in each couple of steps we add one more element to our expressions. Our expressions becomes bigger and bigger until we end when we finally reduce it to the final value.

Tail Recursion

That difference in the rewriting rules actually translates directly to a difference in the actual execution on a computer. In fact, it turns out that if you have a recursive function that calls itself as its last action, then you can reuse the stack frame of that function. This is called tail recursion.

And by applying that trick, a tail recursive function can execute in constant stack space, so it's really just another formulation of an iterative process. We could say a tail recursive function is the functional form of a loop, and it executes just as efficiently as a loop.

If we look back at gcd, we see that in the else part, gcd calls itself as its last action. And that translates to a rewriting sequence that was essentially constant in size, and that will, in the actual execution on a computer, translate into a tail recursive call that can execute in constant space.

On the other hand, if you look at factorial again, then you'll see that after the call to factorial(n - 1), there is still work to be done, namely, we had to multiply the result of that call with the number n. So, that recursive call is not a tail recursive call, and it becomes evident in the reduction sequence, where you see that actually there’s a buildup of intermediate results that we all have to keep until we can compute the final value. So, factorial would not be a tail recursive function.

Both factorial and gcd only call itself but in general, of course, a function could call other functions. So the generalization of tail recursion is that, if the last action of a function consists of calling another function, maybe the same, maybe some other function, the stack frame could be reused for both functions. Such calls are called tail calls.

Tail Recursion in Scala

In Scala, only directly recursive calls to the current function are optimized.

One can require that a function is tail-recursive using a @tailrec annotation:

@tailrec
def gcd(a: Int, b: Int): Int = …

If the annotation is given, and the implementation of gcd were not tail recursive, an error would be issued.

Exercise

Complete the following definition of a tail-recursive version of factorial:

def factorial(n: Int): Int = {
  @tailrec
  def iter(x: Int, result: Int): Int =
    if (x == res0) result
    else iter(x - 1, result * x)

  iter(n, res1)
}

factorial(3) shouldBe 6
factorial(4) shouldBe 24