How does @tailrec work

Question

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

Answer 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

  }