recursion - Is there a way to optimize tail calls in Scala?

Question

I am aware that Scala has optimizations for tail-recursive functions (i.e. those functions in which the recursive call is the last thing executed by the function). What I am asking here is whether there is a way to optimize tail calls to different functions. Consider the following Scala code:

def doA(): Unit = {
  doB()
}

def doB(): Unit = {
  doA()
}

If we let this execute long enough it will give a stack overflow error which one can mitigate by allocating more stack space. Nonetheless, it will eventually exceed the allocated space and once again cause a stack overflow error. One way to mitigate this could be:

case class C(f: () => C)

def run(): Unit = {
  var c: C = C(() => doA())
  while(true){
    c = c.f.apply()
  }
}

def doA(): C = {
  C(() => doB())
}

def doB(): C = {
  C(() => doA())
}

However, this proved to be quite slow. Is there a better way to optimize this?

question from:https://stackoverflow.com/questions/65868273/is-there-a-way-to-optimize-tail-calls-in-scala

Answer 1

Here's one way achieve an infinite progression of method calls, without consuming stack, where each method decides which method goes next.

def doA(): () => Any = {
  doB _
}
def doB(): () => Any = {
  doC _
}
def doC(): () => Any = {
  if (util.Random.nextBoolean()) doA _
  else                           doB _
}

Iterator.iterate(doA())(_.asInstanceOf[() => () => Any]())
        .foreach(identity)