Asserting @tailrec on Option.getOrElse

In the following, the line maybeNext.map{rec}.getOrElse(n) uses the Option monad to implement the recurse or escape pattern.

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

Looks good, however:

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

I feel that the compiler should be able to sort out tail recursion in this case. It is equivalent to the following (somewhat repulsive, but compilable) sample:

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

Can anyone provide illumination here? Why can't the compiler figure it out? Is it a bug, or an oversight? Is the problem too difficult?

Edit: Remove the @tailrec from the first example and the method compiles; the loop terminates. The last call is always getOrElse which is equivalent to if option.isEmpty defaultValue else recurse. I think this could and should be inferred by the compiler.

---

It is not a bug, it is not an oversight, and it is not a tail recursion.

Yes, you can write the code in a tail recursive manner, but that doesn't mean every equivalent algorithm can be made tail recursive. Let's take this code:

maybeNext.map{rec].getOrElse(n)

First, the last call is to getOrElse(n). This call is not optional -- it is always made, and it is necessary to adjust the result. But let's ignore that.

The next to last call is to map{rec}. Not to rec. In fact, rec is not called at all in your code! Some other function calls it (and, in fact, it is not the last call on map either), but not your function.

For something to be tail recursive, you need to be able to replace the call with a "goto", so to speak. Like this:

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
   }                         
}

How would that happen in the other code?

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)                 
}

The goto here is not inside rec. It is inside an anonymous Function1's apply, which, by its turn, is inside an Option's map, so a branch here would leave two stack frames on each call. Assuming inter-method branching was possible in first place.