Как работает @tailrec

Я использовал и читал об аннотации @tailrec, чтобы иметь хвостовой рекурсивный метод. Я объяснил это многими ссылками. Например, он работает только тогда, когда для функций самообслуживания и не должен превышать и т.д.

Всюду упоминается, что compiler optimizes. Но какая магия/концепция делает компилятор, чтобы сделать его хвостом рекурсивным. Для простой функции ниже, что делает компилятор:

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

Я имею в виду, он преобразует его в цикл, где он повторно вызывает его, а затем возвращает окончательное значение? Есть ли ссылка на бумагу, которая объясняет это.

Ответ 1

В дополнение к моему комментарию по вашему вопросу (копия кода здесь):

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

Я попытался скомпилировать метод fact с недавней сборкой, с которой я только что столкнулся, и с scalac -Xprint:all, и каким-то образом компилятор выпустил файл icode. Таким образом, это действительно иллюстрирует, как он оптимизирует хвостовой вызов:

  // 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 comment: IF condition is here
    3   LOAD_LOCAL(value n)
    3   CONSTANT(1)
    3   CJUMP (INT)LE ? 3 : 4

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

  5: 
    2   RETURN(INT)

  4: // huynhjl 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

Вот хороший Сообщение в блоге по теме

@tailrec только гарантирует, что ошибка выдается, если оптимизация хвостового вызова не может быть выполнена компилятором. Scala выполняет оптимизацию хвостового вызова по умолчанию.

Когда условия, описанные в документе, выполнены, можно сохранить последний кадр вместо стека кадров и выполнить цикл. Процесс лучше описан здесь