如何制作也可以以非尾递归方式引用自身的尾递归方法

Question

假设我有一种用于长时间运行的计算的机制，该机制可以使自身暂停以在以后恢复：

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

最简单的运行方式是

@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());
    }
  }

问题在于创建这样的计算。假设我们要实现尾递归阶乘，它每10个周期暂停一次计算：

@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)
}

但是无法编译：

错误：无法优化@tailrec带注释的方法factorial：它包含不在尾部的递归调用

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

如何在未挂起的电话上保留尾递归？

Answer 1

我找到了一个可能的答案。我们可以将尾递归部分移入内部函数，并在需要时引用外部的非尾递归部分：

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)
}