CODEWITHSUNDEEP
scalatail-recursion
user3467471
user3467471

Reputation: 147

Some specific sort of tail-recursion in scala

I would like to understand, how those sort of tail-recursion will be executed under the hood, I saw recently in one of the big-data assignment written in scala. I provide also two additional versions of the implementation, how I would rather write this code - one of them is also tail-recursive, and the other one - not; However, I would like to understand, how the first implementation, provides the same result.

So, here it is (aim is to find an index of the specific name (tag) in the list (ls)):

def firstLangInTag(tag: Option[String], ls: List[String]): Option[Int] = {
if (tag.isEmpty) None
else if (ls.isEmpty) None
else if (tag.get == ls.head) Some(0)
else {
  val tmp = firstLangInTag(tag, ls.tail)
  tmp match {
     case None => None
     case Some(i) => Some(i + 1)
     }
  }
}

When we think about execution, it will be seen as follows for parameters 'tag' defined as Option("Scala"), and 'ls' as List("Java", "PHP", "Scala"):

So we have an answer Some(2) and it is correct, but could someone please explain, where is var 'i' (implicated var 'tmp') saved during execution. Is it because, tail-recursion provides one stack for each recursive execution and 'i' just saved in memory and will be updated every time during iteration? Why var 'tmp' will not just overwritten by each iteration, but rather the result will accumulated (+ 1). If you look at following implementations with 'accumulator', but recursive again, then it is pretty clear, that result have been stored in variable called 'acc', thus 'acc' returns the result of this function:

def firstLangInTag(tag: Option[String], ls: List[String]): Option[Int] = {
   def counter(acc: Int, tag: Option[String], ls: List[String]): Int = {
     if (tag.isEmpty) acc
     else if (ls.isEmpty) acc
     else if (tag.get == ls.head) acc
     else counter(acc + 1, tag, ls.tail) 
   }
   Option(counter(0, tag, ls))

Similarly, we can also achieve the same result as not tail-recursive function (providing that, it will be returned Int instead of Option):

...
else 1 + firstLangInTag(tag, ls.tail);

But, please, could someone explain me the first function and how scala makes it possible to store the result in the VAL and in addition update it by each next iteration;

Thank you in advance!

Upvotes: 0

Views: 333

Answers (3)

Joe K
Joe K

Reputation: 18424

The first given function is not tail-recursive. Add the @scala.annotation.tailrec annotation to it, and compilation fails. You are right to be skeptical of how the part dealing with tmp and i works since that's precisely the part that prevents it from being tail-recursive.

Upvotes: 0

sebarys
sebarys

Reputation: 11

E.g val tmp = firstLangInTag(Some("Scala"), List("PHP", "C#", "Scala")) => returns Some(2)

In above example you will have three calls of your function. Every earlier to return the result has to wait for execution following him:

  • 1st firstLangInTag(Some("Scala"), List("PHP", "C#", "Scala"))
  • 2nd firstLangInTag(Some("Scala"), List("C#", "Scala"))
  • 3rd firstLangInTag(Some("Scala"), List("Scala"))

Last call will return Some(0) which will be propagated to the second call where tmp will be resolved as Some(0) and returned to the first call Some(1).

Finally, the first call tmp will be resolved as Some(1) then matched and function will return Some(2).

The first solution in not tail-recursive because first call of the function need wait to the function call (with the tail of the list) that find tag or return None in case of lack of tag in initial list.

To resolve this without unnecessary overhead on the stack using the version with accumulator and add @tailrec annotation

When you try to write tail-recursive function you always could add a @tailrec annotation so that you can be sure if function is not implemented properly you will receive an error message.

Upvotes: 0

Sam Hazleton
Sam Hazleton

Reputation: 462

I'll let someone who is more versed in Scala give a more detailed answer about the contents of the stack at each phase of execution, but I do notice that tmp is set to the return value of a function. No intermediate values are being stored while the list is being traversed in the forward direction, but each call to firstLangIntTag applies a function to the result of the call returning to it. This is possible because functions are objects in Scala.

Upvotes: 0

Related Questions