尾递归的循环优化尾递归即是递归调用放在方法末尾的递归方式如经典的阶乘span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffint /spanFactorialTailRecursion(span stylecolor:#0000ffint /spann, span stylecolor:#0000ffint /spanacc) { span stylecolor:#0000ffif /span(n 0) span stylecolor:#0000ffreturn /spanacc; span stylecolor:#0000ffreturn /spanFactorialTailRecursion(n - 1, acc * n); } /span/span由于递归在方法的末尾因此方法中的局部变量已经毫无用处编译器完全可以将其“复用”并把尾递归优化为“循环”方式span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffint /spanFactorialLoopOptimized(span stylecolor:#0000ffint /spann, span stylecolor:#0000ffint /spanacc) { span stylecolor:#0000ffwhile /span(span stylecolor:#0000fftrue/span) { span stylecolor:#0000ffif /span(n 0) span stylecolor:#0000ffreturn /spanacc; acc * n; n--; } } /span/span不过上文还提到了尾递归中的常用技巧Continuation。那么对于如下形式的Continuation编译器又该如何优化呢span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffint /spanFactorialContinuation(span stylecolor:#0000ffint /spann, span stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span continuation) { span stylecolor:#0000ffif /span(n 0) span stylecolor:#0000ffreturn /spancontinuation(1); span stylecolor:#0000ffreturn /spanFactorialContinuation(n - 1, r continuation(n * r)); } /span/span我们先用“人脑”来思考一下这段代码的执行方式是怎么样的。我们每次使用n和contn调用FactorialContinuation时都会构造一个新的contn - 1并同n - 1传入下一次FactorialContinuation调用中去。以此类推直到n等于0时就直接调用cont0并返回。至于每个Continuation的定义我们可以归纳出如下结果Funcint,int contn r r * n因此Factorial(n) contn(contn - 1(...(cont2(cont1(cont0(1)))...)) n * ((n – 1) * (...(2 * (1 * 1))...)) n * (n - 1) * ... * 2 * 1 n!于是我们可以根据这个“意图”将FactorialContinuation方法“优化”为如下形式span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffint /spanFactorialLoopOptimized2(span stylecolor:#0000ffint /spann, span stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span continuation) { span stylecolor:#2b91afLinkedList/spanspan stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span contList span stylecolor:#0000ffnew /spanspan stylecolor:#2b91afLinkedList/spanspan stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span(); span stylecolor:#0000ffwhile /span(span stylecolor:#0000fftrue/span) { span stylecolor:#0000ffif /span(n 0) span stylecolor:#0000ffbreak/span; span stylecolor:#0000ffint /spantempN n; span stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span newCont r tempN * r; contList.AddFirst(newCont); n--; continuation newCont; } span stylecolor:#0000ffreturn /spancontList.Aggregate(1, (acc, cont) cont(acc)); } /span/span我们构造了一个Continuation函数链表随着n递减每次都会把新的Continuation函数插入到链表头最后Aggregate方法会将第一个参数累加器依次运用到每个函数中去得到最后结果并返回。只可惜这个优化完全是我们“一厢情愿”而已这么做的前提是“理解”了函数的意义把方法的迭代调用“拆开”而编译器是无法还是很难帮我们优化到如斯地步的。那么编译器对于此类问题又该如何解决呢之前我们使用C#中的匿名方法特性来构造每个Continuation方法。如果我们使用自定义的封装类再将递归“优化”成循环FactorialContinuation又会成为什么样呢如下span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffprivate class /spanspan stylecolor:#2b91afContinuation /span{ span stylecolor:#0000ffpublic /spanContinuation(span stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span cont, span stylecolor:#0000ffint /spann) { span stylecolor:#0000ffthis/span.cont cont; span stylecolor:#0000ffthis/span.n n; } span stylecolor:#0000ffprivate /spanspan stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span cont; span stylecolor:#0000ffprivate int /spann; span stylecolor:#0000ffpublic int /spanInvoke(span stylecolor:#0000ffint /spanr) { span stylecolor:#0000ffreturn this/span.cont(span stylecolor:#0000ffthis/span.n * r); } } span stylecolor:#0000ffpublic static int /spanFactorialLoopOptimized3(span stylecolor:#0000ffint /spann, span stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span continuation) { span stylecolor:#0000ffwhile /span(span stylecolor:#0000fftrue/span) { span stylecolor:#0000ffif /span(n 0) span stylecolor:#0000ffbreak/span; continuation span stylecolor:#0000ffnew /spanspan stylecolor:#2b91afContinuation/span(continuation, n).Invoke; n--; } span stylecolor:#0000ffreturn /spancontinuation(1); } /span/span其实这才是FactorialContinuation的“直译”也是编译器能够进行优化。不过朋友们应该也能够看出这只是一个Continuation对象套着另一个Continuation对象。如果形成了数万个Continuation对象的嵌套在最终调用最外层的Continuation时每个内部的Continuation也会在调用时往同一个堆栈中不断累加最终还是会造成堆栈溢出。因此如果使用了Continuation还是无法简单把递归优化成循环来避免堆栈溢出的。编译器还必须进行其他方面的优化。方法尾调用的优化上一篇文章曾经谈到“与普通递归相比由于尾递归的调用处于方法的最后因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义因此完全可以把本次方法中留在堆栈中的数据完全清除把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积意味着即时是“无限”递归也不会让堆栈溢出”。这其实才是尾递归的“正统”优化方式那么我们先暂时忘记之前的“循环优化”从最简单的示例中查看这样的优化是如何进行的。还是最简单的“尾递归”阶乘span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffstatic int /spanFactorialTailRecursion(span stylecolor:#0000ffint /spann, span stylecolor:#0000ffint /spanacc) { span stylecolor:#0000ffif /span(n 0) span stylecolor:#0000ffreturn /spanacc; span stylecolor:#0000ffreturn /spanFactorialTailRecursion(n - 1, acc * n); } /span/span它的IL代码是span stylecolor:#333333span stylebackground-color:#ffffff.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 // 返回递归调用结果 } /span/span在这个问题上我们还需要观察它的汇编代码为了不干扰文章内容我会把获取汇编代码的做法单独写一篇文章稍后发布如下span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#ff000000ad00d0/span 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的值即为span stylecolor:#ff000000ad00d0/span) 00ad00f9 pop esi 00ad00fa pop ebp 00ad00fb ret /span/span上面的汇编代码非常简单从中可以看出每次递归调用都使用了最简单的call指令没有经过任何有效的优化或调整。因此在不断地递归调用之后终究会出现堆栈溢出。这就是普通递归的缺陷。而对于尾递归来说MSIL提供了额外的tail指令表示“尾调用”1它只需简单补充在IL指令call, callvirt, calli之前便可。因此我们使用ildasm.exe将IL代码dump出来并在call之前加上tail指令span stylecolor:#333333span stylebackground-color:#ffffff.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 span stylecolor:#ff0000L_000b: tail./span L_000c: call int32 TailRecursion.Recursion::FactorialTailRecursion(int32, int32) L_0010: ret } /span/span使用ilasm.exe重新编译之后运行再重新察看FactorialTailRecursion的汇编代码span stylecolor:#333333span stylebackground-color:#ffffff00a600d0 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/span/span在这里我实在无法完整讲述上述汇编代码的含义不过从中可以看出它的确对于尾递归进行了特别的处理而并非使用简单的call