O'Reilly logo

Scala Functional Programming Patterns by Atul S. Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Tail recursion to the rescue

There is a technique, an optimization really, that helps us get out of the logjam. However, we need to tweak the code a bit for this. We will make the recursive call as the last and only call. This means that there is no intermediate context to remember. This last and only call is called the tail call. Code in this tail call form is amenable to TCO. Scala generates code that, behind the scenes, uses a loop—the generated code does not use any stack frames:

import 
scala.annotation.tailrec

def count(list: List[Int]): Int = {
  @tailrec   // 1
  def countIt(l: List[Int], acc: Int): Int = l match 
{
  
  case Nil => acc // 2
    case head :: tail => countIt(tail, acc+1) // 3 
  }
  countIt(list, 0)
}

The changes are like this:

We ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required