如何编写一个尾递归方法，使其还能以非尾递归方式引用自身？（涉及IT技术）

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

但是这个无法编译：

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

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

如何在非挂起调用中保留尾递归？

- Petr

---

只是提供信息：LongRunning 是偏函数单子！ - Mysterious Dan

@MyseriousDan 谢谢，这非常有趣。实际上，“LongRunning”是我原始问题的简化 - 我正在为Scala scala-conduit编写一个类似于conduit的库，其中“Pipe”自然形成一个单子。 - Petr

嗯，那种东西通常是某种自由单子的实例化。部分性有点奇怪，因为它通常表示为一个核心递归惰性计算，但是无论你是否拥有 Free[() => _, R] 或者 Free[ChunkOfData => _, R]，在根本上都没有什么区别。 - Mysterious Dan

还要注意的是，这个已经存在于标准库中：http://www.scala-lang.org/api/current/index.html#scala.util.control.TailCalls$ - Régis Jean-Gilles

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

- Petr

---

我说的对吗，这会在每次调用factorial时重新创建闭包实例吗？ - om-nom-nom

@om-nom-nom 我不太确定Scala在优化这样的闭包方面表现如何。无论如何，它们仅用于悬挂，这种情况并不经常发生。（此示例有点简化。）但是从我的观察中可以得出，内存占用保持恒定。我测试了另一个类似的计算，使用了1000000个悬挂。它运行非常快，仅消耗很少的内存。 - Petr

我说这样做会在每次阶乘调用时重新创建闭包实例，这样说对吗？不是的，只有在挂起时才会创建闭包。当 f 调用自身时，该调用确实是尾递归的，因此没有进一步的堆栈使用（因此也没有堆栈溢出）。 - Régis Jean-Gilles