Tail Recursion

After tremendous success of my last post 😁😆, (https://www.garudax.id/pulse/reverse-linked-list-group-k-scala-mrigank-sagar-ejwzc/?trackingId=SWFKN1VMQfK2MPh3fvO9MQ%3D%3D)

I invite you to have a look at tail recursion optimisation with me.

❓So what is Tail recursion Optimisation.

➡ Whenever a function calls another function or itself recursively, it uses stack frames to keep track.

❓But Is it always necessary to keep the track in stack frames (it uses memory after all)

➡ In case of tail recursion,

• A function does some computation, then
• Call the same function recursively
• but It does not compute again after the recursive call is returned, and indeed return the value returned by recursive call

Here keeping the caller in stack is not necessary, and can be avoided to save memory in stack.

This is called tail recursion optimisation in short.

Lets review the code from previous post:

This computes reverse linked list by group of K

def reverseInKgroup[A] (k:Int) (list: List[A]): List[A] =
  if list.isEmpty then return Nil
  val (part1, part2) = list splitAt k
  part1.reverse ::: reverseInKgroup (k) (part2)        

But It doesn't use tail recursion Optimisation, lets try to do it.

Welcome to Annotation

"@tailrec"

we use it before function definition to tell the compiler to tail recursion optimise it (even though compiler optimise it without telling it) so more of a marker to ourselves.

But tail recursive code has to return the recursive call and not do any computation after recursive call. So lets change the code.

The changes are

1. Pass the computed result toward the tail (recursive call) which initially would be Nil ( List[Nothing] in other words or an empty list)
2. It includes a helper function (which is marked as @tailrec) inside the function itself , which was needed to support the accumulated result which is absent in the original function (parameter named as done)
3. After we have travelled the List completely we return the result (saved in "done" parameter)

def reverseInKgroup[A] (k:Int) (list: List[A]): List[A] =
  @tailrec
  def helper(done:List[A], leftTodo: List[A]):List[A] =
    if list.isEmpty then return done
    val (part1, part2) = list splitAt k
    helper(done:::part1.reverse, part2)

  helper(Nil, list)        

Is This Really Better 🤔?

Let's analyse the complexity of the ::: operator:

done::: part1.reverse        

• It has a linear time complexity relative to the length of the first operand i.e "done". Cause Appending a linked list takes linear time.

Lets analyse the complexity of the helper function now!

In the original code, done always has a length of k. And it is done exactly n/k times

which leads to k times n/k which in n. It is linear in "n".

However, in the new code, the length of done keeps increasing by k: 1st time (k), 2nd time (2k), and so on till N.

So it is, k + 2k + 3k + 4k + ........ ..... + n-k + n.

this mathematical expression is quadratic.

Therefore, the original code has a linear time complexity, while the new code has a quadratic complexity, which is much worse.

MORAL of the Story

1. Don't force tail recursion.
2. Godzilla is more powerful than Kong.

Hope you had fun.

Best - Mrigank