RECURSION / TAIL RECURSION IN SCALA

Recursion

Recursion is a function which calls itself over and over again until an exit condition is met. It breaks down a large problem into a smaller problem, solves the smaller parts, and combines them to produce a solution. Recursion could be applied to many common problems, which can be solved using loops, for and while.

Why Recursion?

1. The code is simpler and shorter than an iterative code as we only need to define the base case and recursive case.
2. It avoids the mutable variables that you need to use while writing loops.

Reverse of a List using Recursion

def reverse[A](inputList: List[A]): List[A] = inputList match {
    case head :: tail => reverse(tail) ::: List(head)
    case Nil => Nil
  }

In the above function, when the list is empty we are returning Nil. When the list is non-empty we are concatenating the List with the head element by recursively calling the reverse method with the tail elements. The chain of calls is pushed onto the stack, each one waiting for the next one to return before it concatenates the List and returns.

When we pass List(1,2,3,4,5) into the reverse function, the calls will be :-

reverse(List(2,3,4,5)) ::: List(1)
reverse(List(3,4,5)) ::: List(2) ::: List(1)
reverse(List(4,5)) ::: List(3) ::: List(2) ::: List(1)
reverse(List(5)) ::: List(4) ::: List(3) ::: List(2) ::: List(1)

Problem with Recursion

1. For every recursive call, separate memory is allocated for the variables.
2. Recursive functions often throw a Stack Overflow Exception when processing or operations are too large.

Example : When we pass a List with 5000 numbers in the above recursive function, the following exception occurs.

Exception in thread "main" java.lang.StackOverflowError
	at com.Reverse.Reverse.reverse(ReverseList.scala:7)
	at com.Reverse.Reverse.reverse(ReverseList.scala:7)
	at com.Reverse.Reverse.reverse(ReverseList.scala:7)
	at com.Reverse.Reverse.reverse(ReverseList.scala:7)

Why Stack Overflow Error occurs?

In a recursive function, every method call will create its stack frame in the stack memory. The first call of the function doesn’t return until the last call in the recursion is resolved. So, the function return order is from last invoked to first invoked. This means that if the function F calls itself recursively for N times, then it would create N stack frames in the stack memory for a single execution of the function F. The compiler will keep all the N stack frames in memory till the recursion is complete.

To solve the stack overflow error we can use tail-recursion.

Tail Recursion

A recursive function is said to be tail-recursive if the recursive call is the last operation performed by the function. There is no need to keep a record of the previous state. In Scala, you can use @tailrec to check if the recursion is tail-recursive or not. The annotation is available in the scala.annotation._ package. If the recursion isn’t tail-recursive, then Scala will throw a compile-time error.
When the Scala compiler recognizes that it is tail-recursion, it will optimize the function by converting it to a loop. We will not realize the change, but the compiler will do it internally. This optimization will overcome the performance and memory problem.

Let’s look at a tail-recursive version of reverse of a List.

def reverseTail[A](inputList: List[A]): List[A] = {
    @tailrec
    def reverse(reversedList: List[A], remainingList: List[A]): List[A] = remainingList match {
      case Nil => reversedList
      case head :: tail => reverse(head :: reversedList, tail)
    }
    reverse(Nil, inputList)
  }

In the above code snippet, we are using an additional new reversedList parameter which saves all the intermediate results and passes its value to recursive method calls. This way the stack doesn’t need to track the subsequent recursive calls. Instead, the function itself knows the actual value of the intermediate result, which introduces a great memory optimization.

Conclusion

Recursion is a very important concept in software irrespective of the programming language. Though it takes more memory, recursion makes code simpler and clearer. It would be a wiser choice to use tail recursion wherever possible as it doesn’t throw a StackOverflowError when the input is large.

REFERENCES: Tail-Recursive Algorithms in Scala