How does @tailrec work

问题:

I have used and read about @tailrec annotation to have a tail recursive method. I have gone through many links that explains it. For example it only works when for self-calling functions and shouldnot be overriden etc.

Everywhere it is mentioned that the compiler optimizes. But what magic/concept does the compiler do to make it tail recursive. For a simple function below, what does the compiler do:

@tailrec def fact(acc: Int, n: Int): Int = {
  if (n <= 1) acc
  else fact(n * acc, n - 1)
}
fact(1,10)

I mean does it convert it into a loop where it repeatedly calls it and then returns the final value? Is there any link to paper which explains it

回答1:

In addition to my comment on your question (repasting the code here):

  var acc = 1 
  var n = 10
start: 
  if (n <= 1) return acc 
  else { 
    acc = n * acc
    n = n - 1
    goto start
  }

I tried compiling the fact method with a recent build I just happened to have and with scalac -Xprint:all and somehow the compiler emitted an icode file. So this really illustrates how it optimizes the tail call:

  // methods
  def fact(acc: Int (INT), n: Int (INT)): Int {
  locals: value acc, value n, value _$this
  startBlock: 1
  blocks: [1,2,3,4,5]

  1: 
    2   JUMP 2

  2: // huynhjl's comment: IF condition is here
    3   LOAD_LOCAL(value n)
    3   CONSTANT(1)
    3   CJUMP (INT)LE ? 3 : 4

  3: // huynhjl's comment: first branch of IF, will return acc
    3   LOAD_LOCAL(value acc)
    3   JUMP 5

  5: 
    2   RETURN(INT)

  4: // huynhjl's comment: else branch of IF, update acc and n and jump back
    4   LOAD_LOCAL(value n)
    4   LOAD_LOCAL(value acc)
    4   CALL_PRIMITIVE(Arithmetic(MUL,INT))
    4   LOAD_LOCAL(value n)
    4   CONSTANT(1)
    4   CALL_PRIMITIVE(Arithmetic(SUB,INT))
    4   STORE_LOCAL(value n)
    4   STORE_LOCAL(value acc)
    4   JUMP 2

  }

回答2:

Here is a nice Blog post on the subject

@tailrec only guarantees that an error is issued if tail call optimization cannot be performed by the compiler. Scala performs tail call optimization by default.

When conditions described by the paper are met, it is possible to keep the last frame, instead of the stack of frames, and to perform a loop. The process is better described here