Scala tail recursion by example
Tags: scala, jvm, java, functional
Published: 2020-08-10 12:38:05

A tail recursive function in [Scala ](https://www.scala-lang.org/)is remedy if your recursive functions causes a [stack overflow](https://en.wikipedia.org/wiki/Stack_overflow). Furthermore, [tail recursion](https://en.wikipedia.org/wiki/Tail_call) is a great way if to make your code faster and memory constant. With this in mind, let’s dive into how tail recursion can be implemented in Scala.

The functional programming paradigm used in conjunction with Scala, promotes the usage of recursion for iterating over collections. In contrast to widely used *loops* or *map* functions, recursive iterations may reveal faster and more memory efficient. In general, recursion can be phrased as:
>  *Recursion solves the [recursive problems](https://en.wikipedia.org/wiki/Recursion) by using [functions](https://en.wikipedia.org/wiki/Function_(computer_science)) that call themselves from within their own code.*
>  [*Wikipedia](https://en.wikipedia.org/wiki/Recursion_(computer_science))*

The problem that exists is that repeated call of standard recursive functions may overflow the execution stack, causing the program to crash.

## Tail recursion

Scala tail recursion solves the problem of stack overflow. Moreover, it handles the memory heavy numerical operations on large numbers, which can overflow the stack as well. A tail recursive functions’s last expression has to be a call to another recursive function. Because of that, records of the previous state doesn’t have to be kept.

Let’s learn how this works by looking at the example. Firstly, we define a factorial function as a standard recursive function. As the name suggests, the *factorial* functions counts the factorial of an arbitrary number.

    def factorial(n: Int): Int = {
      if (n <= 1) 1
      else n * factorial(n - 1)
    }

The code above is quite simple — return the multiplication of a number and a factorial of number before, until the number is not equal or less than 1. The last expression in this example, is a mathematical operation. To make this a tail recursive function, the last expression should be **exclusively **call to a recursive functions. Let’s refactor this example and write the tail recursive equivalent:

    import scala.annotation.tailrec

    def tailRecFactorial(n: Int): BigInt = {
        @tailrec
        def factorialHelper(x: Int, accumulator: BigInt): BigInt = {
          if (x <= 1) accumulator
          else factorialHelper(x - 1, x * accumulator)
        }
        factorialHelper(n, 1)
      }

First thing to note is the inclusion of import statement. This imports the **@tailrec** annotation, which explicitly marks the function as tail recursive. The tailRecFactorial functions, uses a helper function factorialHelper that does all the heavy lifting. The core this here is the **accumulator** parameter - this parameter saves all the intermediate results and passes its value to recursive method calls. This way the stack doesn't have to track the subsequent recursive calls. Instead, the function itself knows the actual value of intermediate result, which introduces a great memory optimization.

And that’s really it. The tail recursive functions are first citizen in Scala and you should use them whenever possible.

## Summary

I hope you have found this post useful. If so, don’t hesitate to like or share this post. Additionally, you can follow me on my social media if you fancy so 🙂

{% twitter 1249801342312484872 %}