@tailrec 如何工作 [英] How does @tailrec work
问题描述
我已经使用并阅读了关于 @tailrec
注释的尾递归方法.我已经浏览了许多解释它的链接.例如,它仅适用于自调用函数,不应被覆盖等.
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
推荐答案
除了我对您的问题的评论(在此处重新粘贴代码):
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
}
我尝试使用我碰巧拥有的最近版本和 scalac -Xprint:all
编译 fact
方法,并且编译器以某种方式发出了 icode代码> 文件.所以这真的说明了它是如何优化尾调用的:
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
}
这篇关于@tailrec 如何工作的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!