FP Module 2 - 101 Scala

Tail Recursion

Call stack

A call stack is a data structure used by the program to store information about the active subroutines (like methods in Java) in a program. The main reason for having a call stack is so that the program can keep track of where a subroutine should return control to once it finishes executing. For example, suppose we have a method “CreateBox” which calls another method “CreateLine” in 4 different places. If the program has finished executing the method CreateLine, then it needs to know where in the CreateBox method it needs to return to. This is why the program uses a call stack – so that it can keep track of these details.

Stack frame

// Factorial implementation
def f(n: Int): Int = if (n > 1) n * f(n-1) else 1

A stack frame is a part of the call stack, and a new stack frame is created every time a subroutine is called. So, in our recursive Factorial method above, a new stack frame is created every time the method is called. The stack frame is used to store all of the variables for one invocation of a routine. So, remember that a call stack is basically a stack of stack frames. The figure bellow illustrates how the stack behaves for the factorial function that is defined above:

Stack overflow

What would happen if there were no base case in our example above? Well, recursive calls will be made continuously, and each time a recursive call is made a new stack frame is created. Every new stack frame created needs more memory, which then means that there is less memory on the call stack. The call stack has limited memory, which is usually determined at the start of the program – and when that limited memory is exceeded then the stack is said to overflow, which will usually result in the program crashing. So, if we did not have a base case, then the stack would overflow.

The same thing can append with a big number (for example f(10000)). When the number of recursion can be huge, recursion is not an acceptable solution. This is where tail recursion comes in help.

What is tail Recursion ?

Tail recursion is a pattern of use that can be compiled or interpreted as iteration, avoiding the inefficiencies shown in the last section. A tail recursive function is one where every recursive call is the last thing done by the function before returning and thus produces the function's value.

How to do tail Recursion in Scala ?

To take the factorial example and make it tail recursive, we must make sure that the last action performed in the function is the recursive call.

To do this create a new function into the factorial function to have two parameters. The new accumulator parameter stores the intermediate value, so we are no longer doing a calculation against the value returned from the function like we were before.

def factorial(number: Int) : Int = {
   def factorialWithAccumulator(accumulator: Int, number: Int) : Int = {
       if (number == 1) 
           return accumulator
       else
           factorialWithAccumulator(accumulator * number, number - 1)
   }
   factorialWithAccumulator(1, number)
}

This accumulator technique with an associated function inside the original recursive function is generally used.

@tailrec annotation

Sometime, developer is not sure that the function will be optimized or not by the compiler. Adding the @tailrec annotation makes check by the compiler that this function will be optimized as a tail recursion function.

@tailrec
def factorial(number: Int) : Int = {
   def factorialWithAccumulator(accumulator: Int, number: Int) : Int = {
       if (number == 1) 
           return accumulator
       else
           factorialWithAccumulator(accumulator * number, number - 1)
   }
   factorialWithAccumulator(1, number)
}

If compiler is not intended to do so, this annotation forces a compilation error.