在 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！其他一些函数会调用它（事实上，它也不是 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 不在 rec 内。它位于匿名 Function1 的 apply 内部，而后者又位于 Option 的 map 内部>，因此这里的分支会在每次调用时留下两个堆栈帧。首先假设方法间分支是可能的。