为什么 getOrElse 中的 return 使得尾递归不可能？

Question

我对下面的代码感到困惑：代码是人为的，但我仍然认为它是尾递归的。编译器不同意并产生错误消息：

@annotation.tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  if (l.isEmpty) {
    None.getOrElse( return s )
  }
  listSize(l.tail, s + 1)
}

上面的代码如何使尾部回避成为不可能？为什么编译器告诉我：

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

类似的代码（在 map 中包含 return）可以正常编译：

@annotation.tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  if (l.isEmpty) {
    Some(()).map( return s )
  }
  listSize(l.tail, s + 1)
}

即使通过内联 None.isEmpty 获得的代码也可以正常编译：

@annotation.tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  if (l.isEmpty) {
    if (None.isEmpty) {
      return s
    } else None.get
  }
  listSize(l.tail, s + 1)
}

另一方面，稍微修改了映射 的代码被编译器拒绝 并产生错误：

@annotation.tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  if (l.isEmpty) {
    Some(()).map( x => return s )
  }
  listSize(l.tail, s + 1)
}

Answer 1

return 总是中断递归调用。您应该将代码更改为如下内容：

@tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  l match {
    case Nil => s
    case head :: tail => listSize(tail, s + 1)
  }  
}

Answer 2

我现在无法尝试，但这能解决问题吗？

@annotation.tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  if (l.isEmpty) {
    None.getOrElse( return s )
  } else {
    listSize(l.tail, s + 1)
  }
}

使用 if-else，而不仅仅是 if 将确保 if 语句总是 return 某些东西。

Answer 3

这几乎可以肯定是编译器的错误，或者是部分实现的功能。

这很可能与 Scala 表达式中 return 的实现有关。非本地 return 语句是使用异常实现的，因此当 return 被调用时，会抛出一个 NonLocalReturnException，并且整个表达式被包裹在一个 try-catch 中。我敢打赌 x => return x 被转换为嵌套表达式，当它被包裹在 try-catch 中时，在确定它是否可以使用 @tailrec 时会使编译器感到困惑。我什至会说应该避免将 @tailrec 与非本地 return 结合使用。

在 this blog post or in this 问题中阅读更多关于 return 在 Scala 中的实现。

Answer 4

发生这种情况是因为您的第一个代码段中的 return 是非本地代码段（它嵌套在 lambda 中）。 Scala 使用异常来编译非本地 return 表达式，因此代码由编译器转换为：

@annotation.tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  if (l.isEmpty) {
    None.getOrElse( return s )
  }
  listSize(l.tail, s + 1)
}

与此相似的东西（用scalac -Xprint:tailcalls编译）：

def listSize2(l : Seq[Any], s: Int = 0): Int = {
  val key = new Object

  try {
    if (l.isEmpty) {
      None.getOrElse {
        throw new scala.runtime.NonLocalReturnControl(key, 0)
      }
    }

    listSize2(l.tail, s + 1)
  } catch {
    case e: scala.runtime.NonLocalReturnControl[Int @unchecked] =>
      if (e.key == key)
        e.value
      else
        throw e
  }
}

最后一点是，当包裹在 try/catch 块中时，递归调用不是尾调用。基本上，这个人为的例子：

def self(a: Int): Int = {
  try {
    self(a)
  } catch {
    case e: Exception => 0
  }
}

类似于这个，显然不是尾递归：

def self(a: Int): Int = {
  if (self(a)) {
    // ...
  } else {
    // ...
  }
}

在某些特定情况下您可以对此进行优化（减少到两个堆栈帧，如果不是一个），但似乎不存在适用于这种情况的通用规则。

此外，此代码段中的 return 表达式不是非局部 return，这就是可以优化函数的原因：

@annotation.tailrec
def listSize(l : Seq[Any], s: Int = 0): Int = {
  if (l.isEmpty) {
    // `return` happens _before_ map `is` called.
    Some(()).map( return s )
  }
  listSize(l.tail, s + 1)
}

上面的代码之所以有效，是因为在 Scala 中，return e 是一个表达式，而不是一个语句。不过，它的类型是 Nothing，它是所有内容的子类型，包括 Unit => X，这是 map 参数所需的类型。虽然评估非常简单，e 在 map 甚至执行之前从封闭函数返回（显然，参数在方法调用之前评估）。这可能会造成混淆，因为您希望 map(return e) 与 map(_ => return e) 一样是 parsed/interpreted，但事实并非如此。

为什么 getOrElse 中的 return 使得尾递归不可能？

Why return in getOrElse makes tail recursion not possible?

scala

recursion

tail-recursion