Recursion

Recursion is a powerful technique for implementing an inverted loop and does not have the drawbacks of the implementation previously discussed. There is one problem with recursion--your stack can grow quite large. Fortunately, the Scala language provides tail recursion optimization to address this. With tail recursion optimization, the recursion is transformed into a simple goto.

The Scala compiler also supports a tailrec annotation for confirming that the code is being optimized for tail recursion. But it places 3 requirements on the annotated function.

1. The function must be private or final.
2. The function must end with a call to itself. And
3. The function must only have one call to itself.

Meeting these three conditions with code that works the same when synchronously or asynchronously calling another actor may not be possible. You can write code that meets these conditions, but it needs to check to see how it has received the responses to its requests. Time now to look at some code.

We will again address the problem of printing a range of numbers and a lot of the code will be the same.

case class Loop(n: Int)
case class I(i: Int)

class P(mb: Mailbox) extends Actor(mb, null) {
  bind (classOf[I], ifunc)
  def ifunc(msg: AnyRef, rf: Any => Unit) {
    println(msg.asInstanceOf[I].i)
    rf(null)
  }
}

The test code will be the same too.

val mb = new Mailbox
val p = new P(mb)
println("synchronous test")
Future(new L(mb, p), Loop(3))
println("asynchronous test")
Future(new L(new Mailbox, p), Loop(3))

It is only the L class which changes, which is where we implement the inverted loop.

class L(mb: Mailbox, a: Actor) extends Actor(mb, null) {
  bind(classOf[Loop], lfunc)
  def lfunc(msg: AnyRef, rf: Any => Unit) {
    val n = msg.asInstanceOf[Loop].n
    if (n < 1) {
      rf(null)
      return
    }
    lrec(n, 0, rf)
  }

  @tailrec private def lrec(n: Int, _i: Int, rf: Any => Unit) {
    var async = false
    var sync = false
    val i = _i + 1
    a(I(i)) {rsp =>
      if (i == n) rf(null)
      else if (async) _lrec(n, i, rf)
      else sync = true
    }
    if (!sync) {
      async = true
      return
    }
    lrec(n, i, rf)
  }

  def _lrec(n: Int, i: Int, rf: Any => Unit) {lrec(n, i, rf)}
}