From Java to Scala: Tail Recursion

James O. Coplien, “To iterate is human, to recurse, divine.”

It’s been almost 20 years since I attended a functional programming course at university. It taught us how to divide a problem into sub problems, and sub- sub-problems until a base case was reached which solved not only the sub problem, but the problem as a whole. Then, in our first Java course, we learned recursion might produce the simplest solution, but each recursive call consumed more memory from the stack. Eventually, the memory would run out and the program would crash with a StackOverflowException. This is unfortunate as recursion is a key concept within functional programming. Luckily, Scala does a much better job with recursion than Java.

Why do we want to use recursion?

• immutability Unlike a iterative approach recursion lets you write solutions to problems without changing the state of any variables. Instead, the calculation is performed as part of the next recursive call and immediately saved to a parameter.
• readability A recursive solution will read like a list of the cases you need to handle, which, uncluttered by loop constructs, is easier to read and understand.

How do we solve a problem using recursion?

1. Identify parameter and return type by looking at what we start with and what we want to produce.
2. Identify the cases which we need to cover: error cases, base cases and recursion cases.
3. Implement simplest case, usually the error case, first.
4. Then, implement base cases.
5. Finally, implement the recursion cases.

Let’s look at a simple user story to demonstrate the technique:
As a secret agent I want to reverse the text of my documents so that I can keep them secret.

1. Our starting data is a String and the result is another String.
2. Our only error case is a null starting value.
3. Our base case is when we have no more characters to reverse.
4. Our only recursion case is everything else.

def reverse(s: String): String = { // (1)
 if (s == null) return null        // (2)
 if (s.tail.isEmpty) return s      // (3)
 reverse(s.tail) + s.head          // (4)
}

Each time reverse calls itself a new frame is added to the stack as the result of reverse(s.tail) is needed before it can be added to s.head. If possible, we want to avoid this to make to protect us from a StackOverflowException. Head and tail is functional programming lingo for the first element and the remaining elements.

Enter Tail Recursion

A function can be called tail recursive when the last thing that happened was a call to itself, and no other recursive calls were made earlier. A clever compiler can then avoid adding a new frame to the stack, thus saving memory. Unlike Java, Scala has this capability.

Our simple reverse function can easily be converted into using tail recursion by adding a variable to track the result. We will also take advantage of the @tailrec annotation which tells the compiler to expect tail recursion and throw an error if that is not the case.

@scala.annotation.tailrec
def reverse_tail(s: String, r: String): String = {
 if (s == null) return null
 if (s.tail.isEmpty) return s.head + r 
 reverse_tail(s.tail, s.head + r)
}

Adding a second parameter is not really ideal, so lets take it a step further by defining a helper function inside reverse_tail to hide the second parameter.

def reverse_tail2(s: String): String = {
 @scala.annotation.tailrec
 def impl(ss: String, r: String): String = {
   if (ss == null) return null
   if (ss.tail.isEmpty) return ss.head + r
   impl(ss.tail, ss.head + r)
 }
 impl(s, “”);
}

To a Java developer this will look weird, but in a functional language this is perfectly normal. Promise.

Next time: A closer look at some of the more common higher order functions used in functional programming.