您不会在当前MS C#编译器生成的任何代码中找到它.您可以在F#编译器生成的代码中找到它,但没有您想象的那么多,原因几乎相反.
现在,首先纠正你的陈述中的一个错误:
ECMA-335,III.2.4规定了尾部.可以在递归函数中使用的前缀.
这不是严格意义上的.该tail.前缀可在尾部调用的调用中使用; 并非所有递归函数都是尾递归,并非所有尾调用都是递归的一部分.
尾调用是对函数的任何调用(包括OOP方法),其中该代码路径中的最后一个操作是进行该调用然后返回它返回的值,或者如果被调用的函数没有返回值则返回.因此:
int DoSomeCalls(int x)
{
if(A(x))
return B(x);
if(DoSomeCalls(x * 2) > 3)
{
int ret = C(x);
return ret;
}
return D(DoSomeCalls(x-1));
}
这里,调用B和D调用尾部调用,因为调用后唯一要做的就是返回它们返回的值.调用C不是尾调用,但可以ret通过直接返回删除冗余赋值来轻松转换为1 .调用A不是尾调用,也不是调用DoSomeCalls,尽管它们是递归的.
现在,正常的函数调用机制是依赖于实现的,但通常涉及保存调用堆栈后可能需要的引入值,将参数放入堆栈和/或寄存器以及当前指令位置(返回) ,移动指令指针,然后当指令指针移回到完成调用之后,从寄存器或堆栈中读取返回值.通过尾调用,可以跳过很多这样的操作,因为调用函数可以使用当前的堆栈帧,然后直接返回到较早的调用者.
该tail.前缀要求,这与呼叫来完成.
虽然这不一定与递归有关,但在谈论递归时你是正确的,因为在递归情况下消除尾调用的好处要大于其他情况; 当实际使用函数调用机制时,在堆栈空间中进行O(n)调用会在堆栈空间中变为O(1),同时减少每个项目的常量时间成本(因此它仍然是O(n)但是,O(n)时间意味着它需要n×k秒,并且我们有一个更小的k).在许多情况下,这可能是有效的呼叫和抛出的呼叫之间的区别StackOverflowException.
现在,在ECMA-335中,有一些案例陈述了如何tail.不能总是被尊重.特别是§III.2.4中的文字指出:
还可以存在防止尾部的特定于实现的限制.在某些情况下服从的前缀.
在最宽松的情况下,我们可以将其解释为在各种情况下都能阻止它.
相反,允许抖动应用所有方式的优化,包括执行尾调用消除,即使它没有被请求 tail.
因此,实际上有四种方法可以在IL中进行尾部消除:
tail.在通话之前使用前缀,并使其受到尊重(不保证).tail.在调用之前不要使用前缀,但是抖动决定以任何方式应用它(甚至不太保证).jmpIL指令实际上是尾部调用消除的一种特殊情况(C#从未使用它,因为它为通常相对较小的增益产生无法验证的代码,尽管它有时是手动编码时最简单的方法,因为它相对简单).(还有一种情况是内联调用,因为它不需要新的堆栈帧,并且实际上通常总体上具有更强的改进,然后通常允许进行进一步的优化,但它不是'通常认为是尾部调用消除的情况,因为它是一个不依赖于尾部调用的调用消除.
现在,抖动的第一个实现倾向于在许多情况下不进行尾部调用消除,即使它是被请求的.
同时在C#方面,有一个决定不发布tail.C#的一般方法没有大量优化生成的代码.有一些优化(特别是死代码删除),但在大多数情况下,因为优化工作可能只是重复由抖动(或甚至妨碍他们)完成的优化的缺点(更复杂意味着更多可能的错误而IL对许多开发人员来说会更加混乱)相对而言超过了好处.使用tail.是一个典型的例子,因为有时坚持尾部调用实际上比使用.NET节省的成本更高,因此如果抖动已经在尝试解决时,这是一个好主意,那么C#编译器将有更大的机会只是在很多时候让事情变得更糟,其余部分没有任何区别.
值得注意的是,编码风格最常见的是C语言,如C#:
现在,来了F#.
通过F#鼓励的功能和声明性编程,在很多情况下,在C#中以迭代方式最自然地完成的事情最自然地通过递归方法完成.人们在攻击C风格的语言时学习将递归的案例转化为迭代代码,人们在F#风格的语言中学习将迭代案例转化为递归代码,将非尾调用递归代码转换为尾调用递归代码.
所以F#使用tail.了很多.
而且它得到StackOverflowException了很多,因为抖动并不尊重它.
这是导致抖动人员增加他们消除尾部呼叫的情况的数量之一,一般情况下甚至进一步tail.使用.
同时,F#人不仅仅依赖于tail.F#的编译器将比C#更强大地优化; 正如我们可以手动重写递归调用一样,在脚注中进行迭代,因此F#编译器在生成IL时会执行相同的操作.
出于这个原因,很多时候你编写一个F#方法,你期望看到一些IL使用tail.,你实际得到的是IL,迭代地做同样的事情.
但是,tail.当方法以相互递归的方式调用另一个方法时,F#仍将使用,如:
let rec even n =
if n = 0 then
true
else
odd (n-1)
and odd n =
if n = 1 then
true
else
even (n-1)
我完全从这个答案中偷走了因为我只用F#玩了一点点所以我宁愿依赖比我更熟悉的人.
在这种情况下,因为尾调用不在单个函数中,所以不能只重写它以在IL编译点消除它,因此它必须希望抖动将消除,并用于tail.增加它会有机会.
*将递归调用转换为迭代的示例将是以递归调用开始,如:
void ClearAllNodes(Node node)
{
if(node != null)
{
node.Value = null;
ClearAllNodes(node.Next)
}
}
最简单的改变是手动添加尾部调用消除功能,通过我们自己设置参数,然后跳回到方法的开头:
void ClearAllNodes(Node node)
{
start:
if(node != null)
{
node.Value = null;
node = node.Next;
goto start;
}
}
由于我们有充分的理由可以避免goto,我们通常会通过更严格定义的循环机制将其更改为相同的东西:
void ClearAllNodes(Node node)
{
while(node != null)
{
node.Value = null;
node = node.Next;
}
}