为什么Scala不会在try/catch中优化尾递归？

Question

在最近的StackOverflow答案中，我提供了以下递归代码：

def retry[T](n: Int)(fn: => T): T = {
  try {
    fn
  } catch {
    case e if n > 1 =>
      retry(n - 1)(fn)
  }
}

如果我添加@tailrec注释，将会得到如下结果：

无法优化@tailrec注释的retry方法：它包含一个不在尾部位置的递归调用。

我已经能够编写一个尾递归替代方案，但我仍然想知道为什么这个方法没有被优化。为什么呢？

- leedm777

---

如果（n>1）- 真的吗？不是n>0或n>=1吗？如果n==1（== 0），会发生什么？ - user unknown

@user unknown - 显然你需要传入总尝试次数，而不是重试次数。 - Rex Kerr

Answer 1

为了进行尾递归优化，这需要转换成以下类似的形式：

def retry[T](n: Int)(fn: => T): T = {
  START:
    try {
      fn
    } catch {
      case e if n > 1 =>
        n = n - 1
        GOTO START
    }
}

当执行GOTO循环时，它必须离开catch块的范围。但在原始的递归版本中，递归调用的执行仍然在catch块内部。如果语言允许这可能改变代码的含义，那么这将不是有效的优化。

编辑：从与Rex Kerr在评论中的讨论中得出结论，在Scala中这是一种保留行为的转换（但只有在没有finally的情况下）。因此，显然Scala编译器尚未认识到没有finally的catch块的最后一个调用处于尾调用位置。

- Ben

---

过多的猜测，其中很多是错误的。字节码不是问题。字节码甚至不能理解catch块，只能作为try块内异常的目标。异常处理规范不会影响这种转换；尝试将其改写为while循环即可！ - Rex Kerr

@Rex，如果有更了解Java字节码的人纠正我，我会很高兴，但我确实是猜测的方式表达的。不过，我不确定我是否理解了你最后的话。尾递归转换是关于自动将代码重写为类似while循环的东西，而在catch块中发生的尾递归显然会阻止编译器这样做。要么这只是一个尚未实现的功能，要么异常处理规范确实影响了这个转换。还是我误解了你？ - Ben

这是一个尚未实现的功能。只要逻辑正确，在这种情况下，如果将跳转移到catch块之外，行为不会有任何不同。相应的迭代代码是var i = n; while(true) { try { return(fn) } catch { case e if i>1 => i -= 1; } }。 - Rex Kerr

Answer 2

我认为将代码转换为尾递归形式的实现转换列表中并不包括遍历异常处理块。这些特别棘手，即使你可以举出应该是合法的示例（正如你已经做到的那样）。 （有许多看起来合法但实际上不合法的情况（例如如果有 finally 块），或需要更复杂的卷绕/展开规则。）

- Rex Kerr

Answer 3

我在 Stack Overflow 上找到了这个解决方案。基本上，使用带有 fn 的 return，这样如果 fn 没有异常抛出，你的函数也不会抛出异常。如果 fn 抛出异常，并且该异常满足条件 n > 1，则该异常将被忽略并在 catch 块后发生递归调用。

@tailrec
def retry[T](n: Int)(fn: => T): T = {
  try {
    return fn
  } catch {
    case e if n > 1 => // fall through to retry below
  }
  retry(n - 1)(fn)
}

- Landon Kuhn