CODEWITHSUNDEEP
scalarecursiontail-recursion
Petr
Petr

Reputation: 63409

How to make a tail-recursive method that can also refer to itself in a non-tail-recursive way

Suppose I have a mechanism for long-running computations that can suspend themselves to be resumed later:

sealed trait LongRunning[+R];
case class Result[+R](result: R) extends LongRunning[R];
case class Suspend[+R](cont: () => LongRunning[R]) extends LongRunning[R];

The simplest way how to run them is

@annotation.tailrec
def repeat[R](body: LongRunning[R]): R =
  body match {
    case Result(r)   => r
    case Suspend(c)  => {
      // perhaps do some other processing here
      println("Continuing suspended computation");
      repeat(c());
    }
  }

The problem is creating such computations. Let's say we want to implement tail-recursive factorial that suspends its computation every 10 cycles:

@annotation.tailrec
def factorial(n: Int, acc: BigInt): LongRunning[BigInt] = {
  if (n <= 1)
    Result(acc);
  else if (n % 10 == 0)
    Suspend(() => factorial(n - 1, acc * n))
  else
    factorial(n - 1, acc * n)
}

But this does not compile:

error: could not optimize @tailrec annotated method factorial: it contains a recursive call not in tail position

Suspend(() => factorial(n - 1, acc * n))

How to retain tail recursion on the non-suspending calls?

Upvotes: 3

Views: 197

Answers (1)

Petr
Petr

Reputation: 63409

I found one possible answer. We can move the tail-recursive part into an inner function, and refer to the outer one, non-tail-recursive, when we need:

def factorial(n: Int, acc: BigInt): LongRunning[BigInt] = {
  @annotation.tailrec
  def f(n: Int, acc: BigInt): LongRunning[BigInt] =
    if (n <= 1)
      Result(acc);
    else if (n % 10 == 0)
      Suspend(() => factorial(n - 1, acc * n))
    else
      f(n - 1, acc * n)
  f(n, acc)
}

Upvotes: 4

Related Questions