scala - 在 Option.getOrElse 上声明 @tailrec

Question

在下面，maybeNext.map{rec}.getOrElse(n) 行使用 Option monad 来实现递归或转义模式。

scala> @tailrec                                          
     | def rec(n: Int): Int = {                          
     |   val maybeNext = if (n >= 99) None else Some(n+1)
     |   maybeNext.map{rec}.getOrElse(n)                 
     | }

看起来不错，但是:

<console>:7: error: could not optimize @tailrec annotated method: 
it contains a recursive call not in tail position
       def rec(n: Int): Int = {
           ^

我觉得这种情况下编译器应该可以解决尾递归的问题。它等价于以下(有点令人反感，但可编译)示例:

scala> @tailrec                                          
     | def rec(n: Int): Int = {                          
     |   val maybeNext = if (n >= 99) None else Some(n+1)
     |   if (maybeNext.isEmpty) n                        
     |   else rec(maybeNext.get)                         
     | }
rec: (n: Int)Int

谁能在这里提供照明？为什么编译器无法解决？这是一个错误，还是一个疏忽？题太难了？

编辑:从第一个示例中删除 @tailrec 并且方法编译；循环终止。最后一次调用始终是 getOrElse，它等价于 if option.isEmpty defaultValue else recurse。我认为这可以而且应该由编译器推断出来。

Answer 1

这不是错误，不是疏忽，也不是尾递归。

是的，您可以编写尾递归方式的代码，但这并不意味着每个等效算法都可以尾递归。我们来看看这段代码:

maybeNext.map{rec].getOrElse(n)

首先，最后一次调用是getOrElse(n)。这个调用不是可选的——它总是被调用，并且需要调整结果。但是让我们忽略这一点。

倒数第二个调用是map{rec}。 不是到rec。事实上，rec 在您的代码中根本没有被调用 !其他一些函数调用它(事实上，它也不是对 map 的最后一次调用)，但不是你的函数。

对于尾递归的东西，你需要能够用“goto”替换调用，可以这么说。像这样:

def rec(n: Int): Int = { 
  BEGINNING:                         
  val maybeNext = if (n >= 99) None else Some(n+1)
  if (maybeNext.isEmpty) n                        
  else { 
    n = maybeNext.get
    goto BEGINNING
   }                         
}

在其他代码中会如何发生这种情况？

def rec(n: Int): Int = {                  
  BEGINNING:        
  val maybeNext = if (n >= 99) None else Some(n+1)
  maybeNext.map{x => n = x; goto BEGINNING}.getOrElse(n)                 
}

这里的 goto 是 not 在 rec 内。它位于匿名 Function1 的 apply 内，而后者又位于 Option 的 map 内>，所以这里的分支会在每次调用时留下两个堆栈帧。首先假设方法间分支是可能的。