@tailrec是如何工作的？

Question

我已经使用过并阅读了关于@tailrec注解的内容，以实现尾递归方法。我查看了许多解释它的链接。例如，它仅在自调用函数中起作用，并且不应该被覆盖等。

到处都提到编译器进行优化。但编译器是通过什么魔法/概念使其成为尾递归的呢？对于下面的简单函数，编译器做了什么：

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

我的意思是它会将它转换成一个循环，反复调用它，然后返回最终值吗？有没有解释它的论文链接？

- Jatin

---

基本上是的，Scala编译器将代码转换为类似于while循环的字节码。它可能正在执行类似于var acc = 1; var n = 10; start: if (n <= 1) return acc else { acc = n * acc; n = n - 1; goto start }的操作。应该可以通过机械化地将所有尾递归替换为转到函数体开头的goto语句来实现。 - huynhjl

Answer 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'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

  }

- huynhjl

Answer 2

这里是一篇关于该主题的不错博客文章

@tailrec仅在编译器无法执行尾调用优化时才会发出错误信息。Scala默认执行尾调用优化。

当论文所描述的条件得到满足时，可以保留最后一帧而非帧栈，并执行循环。该过程在此处更好地描述了。

- Bruno Grieder

---

我看过了。它没有解释清楚。他提到了可以用于非自我递归方法的跳板，但他给出的解决方案不是尾递归的。 - Jatin

不正确：@tailrec 会导致编译错误，而不是警告。 - Vincenzo Maggio

@VincenzoMaggio 好的 - 我指的是警告，它会“警示”你。我会进行编辑。 - Bruno Grieder