Scala 中的尾递归

1. Introduction

Generally speaking, we can separate recursion problems into head and tail recursion. Head recursion carries the risk of a stack overflow error, should the recursion go quite deep.

In this tutorial, we’ll show how Scala’s tail recursion optimizations can address this issue by reducing the call stack to just one frame.

2. Calculating List Length

Let’s try calculating a list’s length using both head- and tail-recursive implementations.

We can express the algorithm to calculate the length of a List of size N as follows:

1. If the list is empty, then return 0
2. If the list is not empty, then add 1 to the length of the list without its first element

First, let’s write the head-recursive implementation:

def recursiveLength(list: List[String]): Long = list match {
    case Nil => 0
    case head :: tail => 1 + recursiveLength(tail)
}

This implementation is the literal translation of the algorithm into Scala. The problem, though, is that the call stack could get awfully deep, possibly resulting in a stack overflow error.

Let’s see how it compares to a tail-recursive one:

@tailrec
def tailRecursiveLength(list: List[String], accumulator: Long): Long = list match {
    case Nil => accumulator
    case head :: tail => tailRecursiveLength(tail, accumulator + 1)
}

Now, there are some important differences in this last implementation:

• The @tailrec annotation needs to be added to the method. This tells the compiler to verify the code has been compiled with tail call optimization
• The last call of the method must be the recursive one

The second point is the most important one when writing tail-recursive methods. If we do this correctly, then Scala can reduce the call stack down to one call.

2.1. Compiler Support

If we make a mistake, the Scala compiler will raise an error.

To demonstrate this, let’s add the @tailrec the annotation to our original recursiveLength method. When compiling the code, we’ll see the following error: “could not optimize @tailrec annotated method recursiveLength: it contains a recursive call not in tail position”.

It might not seem obvious why the first implementation is not tail-recursive. Let’s re-write the second pattern match in a more verbose way to make it clearer:

def recursiveLengthVerbose(list: List[String]): Long = list match {
    case Nil => 0
    case head :: tail => {
        val accumulator = recursiveLengthVerbose(tail)
        1 + accumulator 
    }
}

As we can see, the last call is not recursive. Fortunately, the compiler will catch this for us.

3. Conclusion

Even with a simple problem, it’s easy to reach the limits of a head-recursive implementation. Although the tail-recursive implementation might look less natural, it’s definitively worth aiming for in certain situations.

The Scala compiler does a good job of optimizing the code and warning us when an implementation is not tail-recursive. Let’s leverage it!

As always, the code is available over on GitHub.