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

Basically yes, the scala compiler converts the code the code to bytecode similar to a while loop. It probably is doing something like `var acc = 1; var n = 10; start: if (n <= 1) return acc else { acc = n * acc; n = n - 1; goto start}`. It should be possible to mechanically replace all tail calls with a goto to the start of the body. — huynhjl, Jun 26 '13 at 13:01

score 12 · Accepted Answer · answered Jun 26 '13 at 13:14

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

  }

score 10 · Answer 2 · edited May 23 '17 at 12:00

10

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

edited May 23 '17 at 12:00

Community

1
1

answered Jun 26 '13 at 12:11

Bruno Grieder

28,128
8
69
101

2

I have seen it. It doesn't explain it. He has mentioned about trampolines which can be used to for non-self rescursive methoed. But the solution he has given is not tail-recursive – Jatin Jun 26 '13 at 12:17
1

Not correct: @tailrec issues a compilation error, not a warning – Vincenzo Maggio Jun 26 '13 at 12:59
@VincenzoMaggio ok - I meant warning in the sense "it warns you". I will edit it. – Bruno Grieder Jun 26 '13 at 13:07

How does @tailrec work

2 Answers2

Linked