在 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不在rec里面。它位于一个匿名Function1的apply内，而Option的map内，所以这里的分支会在每次调用时留下两个堆栈帧。首先假设方法间分支是可能的。