浅谈尾递归的优化方式

作者佚名技术来源 NET编程浏览发布时间 2012-07-03

.cont(this.n　*　r);
　　}
}

public　static　int　FactorialLoopOptimized3(int　n,　Func<int,　int>　 continuation)
{
　　while　(true)
　　{
　　　　if　(n　==　0)　break;
　　　　continuation　=　new　Continuation(continuation,　n).Invoke;
　　　　n--;
　　}

　　return　continuation(1);
}

其实这才是FactorialContinuation的“直译”，也是编译器能够进行优化。不过朋友们应该也能够看出，这只是一个Continuation对象套着另一个Continuation对象。如果形成了数万个Continuation对象的嵌套，在最终调用最外层的Continuation时，每个内部的Continuation也会在调用时往同一个堆栈中不断累加，最终还是会造成堆栈溢出。因此，如果使用了Continuation，还是无法简单把递归优化成循环来避免堆栈溢出的。编译器还必须进行其他方面的优化。

方法尾调用的优化

上一篇文章曾经谈到：“与普通递归相比，由于尾递归的调用处于方法的最后，因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义，因此完全可以把本次方法中留在堆栈中的数据完全清除，把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积，意味着即时是“无限”递归也不会让堆栈溢出”。这其实才是尾递归的“正统”优化方式，那么我们先暂时忘记之前的“循环优化”，从最简单的示例中查看这样的优化是如何进行的。还是最简单的“尾递归”阶乘：

static　int　FactorialTailRecursion(int　n,　int　acc) { 　　if　(n　==　0)　 return　acc; 　　return　FactorialTailRecursion(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　pt

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!

分享到：更多

你可能对下面的文章感兴趣

上一篇: ASP.Net 4.0中新增23项功能下一篇: ASP.NET配置文件纵横谈（二）

关于浅谈尾递归的优化方式的所有评论

随机推荐