如何制作一个尾递归方法，它也可以以非尾递归的方式引用自己 [英] 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];

最简单的运行方式是

@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 个周期暂停一次计算:

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

但这不会编译:

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

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?

推荐答案

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

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

这篇关于如何制作一个尾递归方法，它也可以以非尾递归的方式引用自己的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！