Let’s begin by first understanding how a normal recursive function works, and then we will deep-dive into a tail recursive function

Normal Recursion

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.

Example: Recursive function to calculate the factorial of a number.

def factorial(x: Int): Int =
  if (x <= 1) 1 
  else x * factorial (x-1)

e.g for factorial(5), this is how the function will evaluate to

factorial(5)
    |
  5 * factorial (4)
        |
      4 * factorial(3)
            |
          3 * factorial(2)
               |
            2 * factorial (1)
                  |
                  1

So the call stack will go recursive till, it reaches terminating condition, i.e., factorial (1).
And it will go back in stack trace, and calculate the result.

Disadvantage of normal recursive function

  • When we make a normal recursive call, we have to push the return address onto the call stack then jump to the called function.
  • This means that we need a call stack whose size is linear in the depth of the recursive calls.

Tail Recursion

When the last call of a function consists of calling another function(could be same function), then one stack frame is sufficient for function evaluation.

@tailrec annotation, is used to denote a function as a tail recursive function

Below is an example of tail recursive function to calculate factorial of a number.

def factorial(x: Int): Int = {
  
  @tailrec
  def fact(x: Int, sum: Int): Int = {
    if(x <= 1) sum
    else fact(x-1, sum*x)
  }
  
  fact(x, 1)  
}

e.g for a expression factorial(5), the call stack would look like

factorial(5)
    |
  fact(5, 0)
      |
    fact(4, 5)
        |
      fact(3, 20)
           |
        fact(2, 60)
            |
          fact(1, 120)
              |
             120

Tail recursion is important because it can be implemented more efficiently than general recursion.

  1. When we have tail recursion we know that as soon as we return from the recursive call we’re going to immediately return as well, so we can skip the entire chain of recursive functions returning and return straight to the original caller.
  2. That means a tail-recursion can be optimized by compiler.

 

Reference

https://www.coursera.org/learn/progfun1/home/welcome