I've seen this happen to almost every developer I've mentored: you write a recursive function, you make sure the recursive call is on the last line of the method, and you assume the Scala compiler is magically turning it into a loop under the hood. You feel confident until you hit a production dataset with 100,000 elements and your application crashes with a StackOverflowError.

The Myth that "Last Line" Equals "Tail Recursive"

The biggest misconception is that if the recursive call is physically the last line of code in your function, it's automatically optimized. That's simply not true. For Tail Call Optimization (TCO) to work, the recursive call must be the absolute final action the program takes before returning. If the program has to do even one tiny bit of work with the result of that call, the current stack frame cannot be discarded.

Take a look at this common way to sum a list of integers:

def sum(list: List[Int]): Int = {
  if (list.isEmpty) 0
  else list.head + sum(list.tail)
}

At first glance, sum(list.tail) is on the last line. But look closer. The last operation isn't the recursive call; it's the addition. The computer has to call sum(list.tail), wait for it to return a value, and then add list.head to that value. Because it has to "come back" to perform the addition, it must keep the current stack frame alive. Do this 10,000 times, and you've run out of stack space.

Flattening the Stack with Accumulators

To actually get TCO, we have to move the work into the arguments of the call. I usually do this by introducing a "helper" function or a default parameter that acts as an accumulator. This way, the recursive call is the final act—there's nothing left to do but return the result of that call directly to the original caller.

Here is how I would rewrite that sum function to be truly tail-recursive:

import scala.annotation.tailrec

def sum(list: List[Int]): Int = {
  @tailrec
  def loop(remaining: List[Int], accumulator: Int): Int = {
    if (remaining.isEmpty) accumulator
    else loop(remaining.tail, accumulator + remaining.head)
  }

  loop(list, 0)
}

Notice the difference: we aren't adding the result of the call to something else. We are adding the number to the accumulator before we make the call. Now, the compiler can see that the current frame is useless, so it just replaces it with the next one—essentially turning your recursion into a while loop in the bytecode.

The Safety Net: The @tailrec Annotation

I cannot stress this enough: always use the @tailrec annotation. It doesn't actually do the optimization—the compiler does that regardless—but it tells the compiler, "I intend for this to be tail-recursive. If you can't optimize this, throw a compile-time error."

Without that annotation, you're just guessing. With it, the compiler becomes your unit test for stack safety. If you accidentally add a + 1 to the end of your call six months from now, the build will fail, saving you from a nasty production outage.

📋 Practical Task

Implement a Tail-Recursive Greatest Common Divisor (GCD) Calculator

Write a function gcd(a: Int, b: Int): Int that calculates the greatest common divisor of two integers using the Euclidean algorithm.

• The algorithm states that gcd(a, b) is the same as gcd(b, a % b), and the process stops when the second number becomes 0.
• You must use the @tailrec annotation to ensure the function is optimized.
• Ensure the function handles the base case correctly so it doesn't recurse infinitely.

Test your implementation with gcd(48, 18) (which should return 6) and gcd(101, 10) (which should return 1).