Scala tail recursion by example

#scala #jvm #java #functional

A tail recursive function in Scala is remedy if your recursive functions causes a stack overflow. Furthermore, tail recursion 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 by using functions that call themselves from within their own code.
*Wikipedia*

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 🙂

Bartosz Gajda

@bartoszgajda55

How to write a recursive function in Scala that will not make your stack overflow. Improve your Functional Programming with Tail Recursion.

bartoszgajda.com/2020/01/16/sca…

#scala #scalaprogramming #functionalprogramming #development #algorithms #programming #development

20:47 PM - 13 Apr 2020

0 0