浅谈尾递归的优化方式

上面的汇编代码非常简单，从中可以看出，每次递归调用都使用了最简单的call指令，没有经过任何 有效的优化或调整。因此在不断地递归调用之后，终究会出现堆栈溢出。这就是普通递归的缺陷。而对于 尾递归来说，MSIL提供了额外的tail指令表示“尾调用”¹，它只需简单补充在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了