Scala: recursive functions

I enrolled to Functional Programming in Scala specialization on Coursera. It consists of 5 courses which will take around 180 days. First course in the specialization is Functional Programming Principles in Scala. I already completed the first week and learned some stuff about recursive functions. So It’s time to share some knowledge.

Functions are an integral part of modern programming languages. In OOP they are called methods in a functional world their name is functions as you may guess. I’ve already published multiple articles about Scala functions. In this post I want to speak exactly about recursive functions.

Let’s start from the definition. A recursive function is a function which calls itself. That’s why it’s important to have some condition for stop. Of course if you don’t want to create an infinite loop.

Recursion could be applied to many common problems, which you are used to solve with help of regular loops for and while. For example how to calculate sum of numbers between two numbers? We create an array of all elements and then iterate through it, adding all elements.

def standardSum(a: Int, b: Int): Int = {
  if (a > b) 0
  else {
    var result = 0
    for (number <- a to b)
      result += number
    result
  }
}

//55
standardSum(0, 10)

The same result can be achieved with help of recursive function:

def recursiveSum(a: Int, b: Int): Int = {
  if (a > b) 0
  else {
    a + recursiveSum(a+1, b)
  }
}

//55
recursiveSum(0, 10)

As you see we return expression a + recursiveSum(a+1, b) until all elements would be added.

The second one approach is more concise but it has a point of risk – java.lang.StackOverflowError. Since recursion is interpreted by JVM as a regular Java method invocation, it implies usage of one additional frame in the stack per a recursive call. Hence if the number of recursive calls exceed the limit of stack, the StackOverflow error occur.

Read about the structure of the Java Virtual Machine for more details about stacks and frames.

Tail recursion

If you want to be sure that a recursive function would not cause the StackOverflowError, you need to transform it in a tail recursion. What is a tail recursion? Tail recursion is a function where the last action is invocation of a recursive function. Sounds tricky. Let’s consider an example:

def sum(a: Int, b: Int): Int = {

  @tailrec
  def tailRecursionSum(a: Int, b: Int, result: Int): Int = {
    if (a > b)
      result
    else
      tailRecursionSum(a+1, b, result + a)
  }

  tailRecursionSum(a, b, 0)
}

//55
sum(0, 10)

In the code above we declared a function inside of another function. Annotation @tailrec indicates that the function is a tail recursion. It’s not mandatory, but it validates that the function is developed as a tail recursion.

Thank to Scala tail recursion optimization we don’t fear the exception StackOverflowError, because on JVM level this code interprets as a regular loop.

So a tail recursion in Scala is more efficient than a regular recursion. In order to confirm this, I’d like to demonstrate a function which calculates greatest common divisor. Of course I’ll use a tail recursion:

@tailrec
def gcd(a: Int, b: Int): Int = {
  if (b == 0) a
  else gcd(b, a % b)
}

//9
gcd(18, 27)

Try to illustrate each step of the execution for yourself in order to understand how it works.