Recursion /Tail Recursion in Scala

Scala has some advanced features compared to other languages including support for tail recursion. But let’s first look at what it means and why it helps in building recursive algorithms.

Recursion is quite common in the programming world. As you probably know, it’s the process of solving a problem by breaking it down into smaller sub-problems. You can easily spot recursion if you see a method calling itself with a smaller subset of inputs.

Try the following program, it is a good example of recursion where factorials of the passed number are calculated.

object Demo {
   def main(args: Array[String]) {
      for (i <- 1 to 10)
         println( "Factorial of " + i + ": = " + factorial(i) )
   }
   
   def factorial(n: BigInt): BigInt = {  
      if (n <= 1)
         1  
      else    
      n * factorial(n - 1)
   }
}

An overview of tail recursion:-

Tail recursion is a subroutine (function, method) where the last statement is being executed recursively. Simply saying, the last statement in a function calls itself multiple times.

These functions are more perform-ant as they take advantage of tail call optimization. They simply keep calling a function (the function itself) instead of adding a new stack-frame in memory.

Tail recursive functions should pass the state of the current iteration through their arguments.They are immutable (they are passing values as argument, not re-assigning values to the same variables).

Tail call optimization in Scala:-

Scala supports tail recursive functions by performing tail call optimization. It also has a special annotation, @tailrec, to ensure that the method can be executed in a tail recursive manner, otherwise the compiler produces error.

What are the requirements to write a tail recursive function?

1- There has to be an exit condition: without this the function would end up in a never ending loop which is certainly not the goal with any iterative computation. An exit condition can be achieved by using a condition and when the condition is met the function returns a value, otherwise it keeps calling itself with a different set of attribute values.

2 - A tail recursive function has to be able to call itself: this might not happen if the exit condition is met in the first iteration, however all arguments have to be passed to the function itself for any subsequent calls.

3- You need import tailrec annotation before going to write tail recursive program.

Here’s a sample of a tail-recursive function in Scala:

def factorial(n: BigInt): BigInt =
{
@tailrec def factorialAcc(acc: BigInt, n: BigInt): BigInt =
{
if (n <= 1)
acc
else
factorialAcc(n * acc, n — 1)
}
factorialAcc(1, n)
}
// Main method
def main(args:Array[String])
{
println(factorial(5))
}

Thanks Reader for referring my post on this topic !

I’ll discuss other Scala topic in more detail in a future blog post!