Some specific sort of tail-recursion in scala

Question

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"):

val tmp = firstLangInTag(Scala, (PHP, Scala)) => returns Some(2)
val tmp = firstLangInTag(Scala, (Scala)) => returns Some(1)

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!

Sam Hazleton Sam Hazleton · Accepted Answer · 2017-08-22T17:56:42

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.

Some specific sort of tail-recursion in scala

3 Answers