前面的《尾递归与Continuation》提到了尾部递归的概念和示例，但一些朋友对尾部递归的效果抱有疑问。 因此，我想再简单地说明一下末尾递归的优化原理，给大家一定的理性认识。
尾递归的循环优化
尾部递归是指递归调用位于方法末尾的递归方法。 例如，经典阶乘： intfactorialtailrecursion(intn，intacc )
{
if(n==0)返回ACC；
returnfactorialtailrecursion (n-1，acc * n )；
}
方法中的局部变量不再有用，因为递归位于方法的末尾。 编译器可以完全“复用”它，并以“循环”方式优化尾部递归。 intfactorialloopoptimized(intn，intacc )。
{
为wile (真)
{
if(n==0)返回ACC；
acc *=n；
n----；
}
}
但是，也论述了末尾递归中的一般技巧Continuation。 那么，对于以下形式的Continuation，编译器应该如何优化呢？ intfactorialcontinuation(intn，Func continuation ) )。
{
if(n==0)返回继续(1) 1；
returnfactorialcontinuation (n-1，r=continuation ) n*r )；
}
首先，让我们考虑一下如何使用“人脑”执行此代码。 每次使用n和contn调用FactorialContinuation时，都会构建新的contn - 1，并与n - 1一起传递给下一个FactorialContinuation调用。 这样，直接调用cont0返回，直到n变为0。 对于每个Continuation的定义，可以总结为Func contn=r=r * n的结果
因此，factorial(n )为
=contn(contn-1 )…(cont2) cont1 ) cont0(1)…)
=n * ((n1 ) (…) ) )1)…) ) ) ) ) ) ) n * ) ) ) ) ) ) ) n ) ) ) n ) ) n ) n ) ) n ) n ) n ) n ) n ) ) n ) n ) ) ) n ) n ) ) ) ) )
=n*(n-1 ) . *2*1
=n！
因此，根据这个“意图”，可以将FactorialContinuation方法“优化”为以下形式： intfactorialloopoptimized2(intn，Func continuation )。
{
linkedlistcontlist=new linked list (；
为wile (真)
{
if(n==0) break；
inttempN=n；
Func newCont=r=tempN * r；
contlist.addfirst(NewCont )；
n----；
continuation=newCont；
}
returncontlist.aggregate(1，(acc，cont ) cont ) acc )；
}
我们构建了Continuation函数的链表。 随着n的减少，每次都在链表的开头插入新的Continuation函数。 最后一个Aggregate方法将第一个参数(累加器)依次应用于每个函数，并返回最后的结果。 但是，很遗憾，这种优化完全只是我们的“臆断”。 要执行此操作，必须“理解”函数的含义，并“分解”对方法的迭代调用。 编译器不会优化到这一步。 编译器该如何解决这样的问题呢？
以前，我们使用C#匿名方法的特性构建每个Continuation方法。 如果使用自定义包类并将递归“优化”为循环，FactorialContinuation会怎么样？ 如下所示。 private classContinuation{
公共容器(func cont，intn ) )。
{
this.cont=cont；
this.n=n；
}
私有函数；
私有intn；
公共输入索引(intr ) )。
{
returnthis.cont(this.n*r )；
}
}
公共统计信息基础设施优化3 (intn，Func continuation ) )。
{
为wile (真)
{
p>if(n == 0) break;continuation = newContinuation(continuation, n).Invoke;
n--;
}
returncontinuation(1);
}
其实这才是FactorialContinuation的“直译”，也是编译器能够进行优化。不过朋友们应该也能够看出，这只是一个Continuation对象套着另一个Continuation对象。如果形成了数万个Continuation对象的嵌套，在最终调用最外层的Continuation时，每个内部的Continuation也会在调用时往同一个堆栈中不断累加，最终还是会造成堆栈溢出。因此，如果使用了Continuation，还是无法简单把递归优化成循环来避免堆栈溢出的。编译器还必须进行其他方面的优化。
方法尾调用的优化
上一篇文章曾经谈到：“与普通递归相比，由于尾递归的调用处于方法的最后，因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义，因此完全可以把本次方法中留在堆栈中的数据完全清除，把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积，意味着即时是“无限”递归也不会让堆栈溢出”。这其实才是尾递归的“正统”优化方式，那么我们先暂时忘记之前的“循环优化”，从最简单的示例中查看这样的优化是如何进行的。还是最简单的“尾递归”阶乘：static intFactorialTailRecursion(intn, intacc)
{
if(n == 0) returnacc;
returnFactorialTailRecursion(n - 1, acc * n);
}
它的IL代码是：.method private hidebysig static int32 FactorialTailRecursion(int32 n, int32 acc) cil managed
{
.maxstack 8
L_0000: ldarg.0 // 加载第1个参数，即n
L_0001: brtrue.s L_0005 // 如果第一个参数不为0，则跳转到L_0005
L_0003: ldarg.1 // 运行到此，说明第1个参数为0，则加载第2个参数，即acc
L_0004: ret // 返回(刚加载的第2个参数)
L_0005: ldarg.0 // 加载第1个参数，即n
L_0006: ldc.i4.1 // 加载数值1
L_0007: sub // 将两者相减，即n - 1
L_0008: ldarg.1 // 加载第2个参数，即acc
L_0009: ldarg.0 // 加载第1个参数，即n
L_000a: mul // 将两者相乘，即acc * n
// 把n - 1和acc * n作为参数递归调用
L_000b: call int32 TailRecursion.Recursion::FactorialTailRecursion(int32, int32)
L_0010: ret // 返回递归调用结果
}
在这个问题上，我们还需要观察它的汇编代码(为了不干扰文章内容，我会把获取汇编代码的做法单独写一篇文章，稍后发布)，如下：00ad00d0 push ebp
00ad00d1 mov ebp,esp
00ad00d3 push esi
00ad00d4 mov eax,edx
00ad00d6 test ecx,ecx
00ad00d8 jne 00ad00dd
00ad00da pop esi
00ad00db pop ebp
00ad00dc ret
00ad00dd lea edx,[ecx-1]
00ad00e0 imul ecx,eax
00ad00e3 mov esi,ecx
00ad00e5 test edx,edx
00ad00e7 jne 00ad00ed
00ad00e9 mov eax,esi
00ad00eb jmp 00ad00f9
00ad00ed lea ecx,[edx-1]
00ad00f0 imul edx,esi
00ad00f3 call dword ptr ds:[703068h] (地址703068h的值即为00ad00d0)
00ad00f9 pop esi
00ad00fa pop ebp
00ad00fb ret
上面的汇编代码非常简单，从中可以看出，每次递归调用都使用了最简单的call指令，没有经过任何有效的优化或调整。因此在不断地递归调用之后，终究会出现堆栈溢出。这就是普通递归的缺陷。而对于尾递归来说，MSIL提供了额外的tail指令表示“尾调用”1，它只需简单补充在IL指令call, callvirt, calli之前便可。因此我们使用ildasm.exe将IL代码dump出来，并在call之前加上tail指令：.method private hidebysig static int32 FactorialTailRecursion(int32 n, int32 acc) cil managed
{
.maxstack 8
L_0000: ldarg.0
L_0001: brtrue.s L_0005
L_0003: ldarg.1
L_0004: ret
L_0005: ldarg.0
L_0006: ldc.i4.1
L_0007: sub
L_0008: ldarg.1
L_0009: ldarg.0
L_000a: mul
L_000b: tail.
L_000c: call int32 TailRecursion.Recursion::FactorialTailRecursion(int32, int32)
L_0010: ret
}
使用ilasm.exe重新编译之后运行，再重新察看FactorialTailRecursion的汇编代码：00a600d0 push ebp
00a600d1 mov ebp,esp
00a600d3 push edi
00a600d4 push esi
00a600d5 push ebx
00a600d6 mov eax,ecx
00a600d8 mov esi,edx
00a600da test eax,eax
00a600dc jne 00a600e5
00a600de mov eax,esi
00a600e0 pop ebx
00a600e1 pop esi
00a600e2 pop edi
00a600e3 pop ebp
00a600e4 ret
00a600e5 lea ecx,[eax-1]
00a600e8 imul eax,esi
00a600eb mov edx,eax
00a600ed mov eax,dword ptr ds:[813068h]
00a600f3 push 0
00a600f5 push 0
00a600f7 push 1
00a600f9 push eax
00a600fa cmp dword ptr [mscorwks!g_TrapReturningThreads (7204339c)],0
00a60101 je 00a6010c
00a60103 push ecx
00a60104 push edx
00a60105 call mscorwks!JIT_PollGC (71d5c9d3)
00a6010a pop edx
00a6010b pop ecx
00a6010c call mscorwks!JIT_TailCall (71b02890)
00a60111 int 3
在这里我实在无法完整讲述上述汇编代码的含义，不过从中可以看出它的确对于尾递归进行了特别的处理，而并非使用简单的call指令进行调用。对此互联网上的资源也不多，我只找到了Shri Borde的一篇文章，其中简单描述了Whidbey V2(真早)中CLR对于这方面的处理，以及一些相关的考虑，从中似乎能够看出一些苗头来。
让我们再回想之前的问题：Continuation无法通过简单优化为循环来解决递归问题。但是通过观察可以看出，Continuation.Invoke方法中的cont委托调用是最后一条命令，这说明它是一个“尾调用”——虽然不是“尾递归”，不过这已经满足tail指令的要求了：只需和所在方法返回值相同(或兼容)即可。因此，对于Continuation来说，我们也需要进行尾递归的优化。您可以进行尝试，现在无论递归多“深”，都不会使堆栈溢出了。
注1：与tail类似，IL指令jmp也能够用于方法调用。这两条指令都不会在调用栈上堆积数据。tail与jmp的不同之处在于，前者只需要返回值与所在方法相同或兼容即可，而后者需要签名完全相同。您可以想象得到，对于“直接递归”来说，可以使用jmp进行调用，而普通的“尾调用”，则只能使用tail了。