君，已阅读到文档的结尾了呢~~
UNDEF NOTYPE () EXTERNAL | _PRINTFSTRING TABLE SIZE = 0X0 BYTES. . .QUIZWHAT'S "_PRINTF"WHERE IS "PRINTF"...
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
PRINTF("HELLO\N")
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口数据包的发送和接收原理
数据包的发送和接收原理
09-10-22 &匿名提问
有两种是不正常的.第一，发送的数据超多，接收一点，网络常自动掉线。第二，发送的数据一点点，接收的超多，网络超级慢。以上两种网络都让人无法忍受。如何解决了，首先要找到问题的要源。来看第一种，发送的多，说明网络不畅通，数据包到不了目的地。都堵在网络上了。这说明电脑可能有问题，检查所有的电脑是不是有中毒的机器在不断发包。另一种可能是有人在使用BT下载，用SNIFF查看猛发包主机，找到后将它揪出来。还有在使用某些软件会不会出现网络提示错误。比如我在用OE时，提示TCP/IP上有错误，代码0X800CCC0E等，后面发现还是病毒引起的网络故障。清除病毒后没有揭示了。发送很多，接收基本为0的网络那和断线网络没什么区别。第二种，有点类似第一种，包发不出去，一个劲的在接包，那是网络堵塞了。引起网络堵的原因有很多要从根本上改善网络的运行环境这就的从硬件配置上下功夫了，升级网络，比如购买好的功能强点路由设备等。简单的应急就是想办法能以最快的速度解决问题，比如查出网络上有不用的共享资源，将其断开释放网络带宽。再来学习一下理论：每个数据包包括一块数据，服务器发出下一个数据包以前必须得到客户对上一个数据包的确认。如果一个数据包的大小小于512字节，则表示传输结构。如果数据包在传输过程中丢失，发出方会在超时后重新传输最后一个未被确认的数据包。通信的双方都是数据的发出者与接收者，一方传输数据接收应答，另一方发出应答接收数据。大部分的错误会导致连接中断，错误由一个错误的数据包引起。这个包不会被确认，也不会被重新发送，因此另一方无法接收到。如果错误包丢失，则使用超时机制。错误主要是由下面三种情况引起的：不能满足请求，收到的数据包内容错误，而这种错误不能由延时或重发解释，对需要资源的访问丢失（如硬盘满）。丢包率，是一个比率，网络中数据的传输是以发送和接收数据包的形式传输的，理想状态下是发送了多少数据包就能接收到多少数据包，但是由于信号衰减、网络质量等等诸多因素的影响下，并不会出现理想状态的结果，就是不会发多少数据包就能接收到多少。在单位时间内发送的数据包和未收到的数据包的比率就是 丢包率，当然这个数字是越小越好，比如你玩网络游戏，有时候会觉得卡，就是说明丢包率相对较高所致，我想这样解释你应该能明白。 你可以用系统自带的ping命令，比如你要测试与的网络质量，就可以在命令提示符中输入ping 回车，在结果中会有类似这样的结果，英文很简单，我就不解释了 Ping statistics for : Packets: Sent = 4, Received = 4, Lost = 0 (0% loss), Approximate round trip times in milli-seconds: Minimum = 9ms, Maximum = 15ms, Average = 13ms数据在网络中是被分成一各个个数据报传输的,每个数据报中有表示数据信息和提供数据路由的桢.而数据报在一般介质中传播是总有一小部分由于两个终端的距离过大会丢失,而大部分数据包会到达目的终端.所谓网络丢包率是数据包丢失部分与所传数据包总数的比值.正常传输时网络丢包率应该控制在一定范围内.
请登录后再发表评论!
因为你上网的时候多数的时候都是在接收数据，很少向网络发送数据，ADSL就是根据这个原理做的，不对称的
请登录后再发表评论!
已经有很多介绍DOS（Denial of Service，即拒绝服务）攻击的文章，但是，多数人还是不知道DOS到底是什么，它到底是怎么实现的。本文主要介绍DOS的机理和常见的实施方法。因前段时间仔细了解了TCP/IP协议以及RFC文档，有点心得。同时，文中有部分内容参考了Shaft的文章翻译而得。要想了解DOS攻击得实现机理，必须对TCP有一定的了解。所以，本文分为两部分，第一部分介绍一些实现DOS攻击相关的协议，第二部分则介绍DOS的常见方式。 ?? ??什么是DOS攻击 ?? ??DOS：即Denial Of Service，拒绝服务的缩写，可不能认为是微软的dos操作系统了。好象在5?1的时候闹过这样的笑话。拒绝服务，就相当于必胜客在客满的时候不再让人进去一样，呵呵，你想吃馅饼，就必须在门口等吧。DOS攻击即攻击者想办法让目标机器停止提供服务或资源访问，这些资源包括磁盘空间、内存、进程甚至网络带宽，从而阻止正常用户的访问。比如： ?? ??* 试图FLOOD服务器，阻止合法的网络通讯 ?? ??* 破坏两个机器间的连接，阻止访问服务 ?? ??* 阻止特殊用户访问服务 ?? ??* 破坏服务器的服务或者导致服务器死机 ?? ??不过，只有那些比较阴险的攻击者才单独使用DOS攻击，破坏服务器。通常，DOS攻击会被作为一次入侵的一部分，比如，绕过入侵检测系统的时候，通常从用大量的攻击出发，导致入侵检测系统日志过多或者反应迟钝，这样，入侵者就可以在潮水般的攻击中混骗过入侵检测系统。 ?? ??有关TCP协议的东西 ?? ??TCP（transmission control protocol，传输控制协议），是用来在不可靠的因特网上提供可靠的、端到端的字节流通讯协议，在RFC793中有正式定义，还有一些解决错误的东西在RFC 1122中有记录，RFC 1323 ?? ??则有TCP的功能扩展。 ?? ??我们常见到的TCP/IP协议中，IP层不保证将数据报正确传送到目的地，TCP则从本地机器接受用户的数据流，将其分成不超过64K字节的数据片段，将每个数据片段作为单独的IP数据包发送出去，最后在目的地机器中再组合成完整的字节流，TCP协议必须保证可靠性。 ?? ??发送和接收方的TCP传输以数据段的形式交换数据，一个数据段包括一个固定的20字节头，加上可选部分，后面再跟上数据，TCP协议从发送方传送一个数据段的时候，还要启动计时器，当数据段到达目的地后，接收方还要发送回一个数据段，其中有一个确认序号，它等于希望收到的下一个数据段的顺序号，如果计时器在确认信息到达前超时了，发送方会重新发送这个数据段。 上面，我们总体上了解一点TCP协议，重要的是要熟悉TCP的数据头（header）。因为数据流的传输最重要的就是header里面的东西，至于发送的数据，只是header附带上的。客户端和服务端的服务响应就是同header里面的数据相关，两端的信息交流和交换是根据header中的内容实施的，因此，要实现DOS，就必须对header中的内容非常熟悉。 ?? ??下面是TCP数据段头格式。 ?? ??Source Port和 Destination Port :是本地端口和目标端口 ?? ??Sequence Number 和 Acknowledgment Number ：是顺序号和确认号，确认号是希望接收的字节号。这都是32位的， ?? ??在TCP流中，每个数据字节都被编号。 ?? ??Data offset :表明TCP头包含多少个32位字，用来确定头的长度，因为头中可选字段长度是不定的。 ?? ??Reserved : 保留的6位，现在没用，都是0 接下来是6个1位的标志，这是两个计算机数据交流的信息标志。接收和发送断根据这些标志来确定信息流的种类。下面是一些介绍： ?? ??URG：（Urgent Pointer field significant）紧急指针。用到的时候值为1，用来处理避免TCP数据流中断 。 ?? ??ACK：（Acknowledgment field significant）置1时表示确认号（Acknowledgment Number）为合法，为0的时候表示数据段不包含确认信息，确认号被忽略。 ?? ??PSH：（Push Function），PUSH标志的数据，置1时请求的数据段在接收方得到后就可直接送到应用程序，而不必等到缓冲区满时才传送。 ?? ??RST：（Reset the connection）用于复位因某种原因引起出现的错误连接，也用来拒绝非法数据和请求。如果接收到RST位时候，通常发生了某些错误。 ?? ??SYN：（Synchronize sequence numbers）用来建立连接，在连接请求中，SYN=1，ACK=0，连接响应时，SYN=1，ACK=1。即，SYN和ACK来区分Connection Request和Connection Accepted。 ?? ??FIN：（No more data from sender）用来释放连接，表明发送方已经没有数据发送了。 ?? ??知道这重要的6个指示标志后，我们继续来。 16位的WINDOW字段：表示确认了字节后还可以发送多少字节。可以为0，表示已经收到包括确认号减1（即已发送所有数据）在内的所有数据段。 ?? ??接下来是16位的Checksum字段，用来确保可靠性的。 ?? ??16位的Urgent Pointer，和下面的字段我们这里不解释了。不然太多了。呵呵，偷懒啊。 ??我们进入比较重要的一部分：TCP连接握手过程。这个过程简单地分为三步。 ?? ??在没有连接中，接受方（我们针对服务器），服务器处于LISTEN状态，等待其他机器发送连接请求。 ?? ??第一步：客户端发送一个带SYN位的请求，向服务器表示需要连接，比如发送包假设请求序号为10，那么则为：SYN=10，ACK=0， ?? ??然后等待服务器的响应。 ?? ??第二步：服务器接收到这样的请求后，查看是否在LISTEN的是指定的端口，不然，就发送RST=1应答，拒绝建立连接。如果接收 ?? ??连接，那么服务器发送确认，SYN为服务器的一个内码，假设为100，ACK位则是客户端的请求序号加1，本例中发送的数据是： ?? ??SYN=100，ACK=11，用这样的数据发送给客户端。向客户端表示，服务器连接已经准备好了，等待客户端的确认 ?? ??这时客户端接收到消息后，分析得到的信息，准备发送确认连接信号到服务器 ?? ??第三步：客户端发送确认建立连接的消息给服务器。确认信息的SYN位是服务器发送的ACK位，ACK位是服务器发送的SYN位加1。 ?? ??即：SYN=11，ACK=101。 ?? ??这时，连接已经建立起来了。然后发送数据，。这是一个基本的请求和连接过程。需要注意的是这些标志位的关系，比如SYN、ACK。 ?? ??服务器的缓冲区队列（Backlog Queue） ?? ??服务器不会在每次接收到SYN请求就立刻同客户端建立连接，而是为连接请求分配内存空间，建立会话，并放到一个等待队列中。如果，这个等待的队列已经满了，那么，服务器就不在为新的连接分配任何东西，直接丢弃新的请求。如果到了这样的地步，服务器就是拒绝服务了。 ?? ??如果服务器接收到一个RST位信息，那么就认为这是一个有错误的数据段，会根据客户端IP，把这样的连接在缓冲区队列中清除掉。这对IP欺骗有影响，也能被利用来做DOS攻击。 上面的介绍，我们了解TCP协议，以及连接过程。要对SERVER实施拒绝服务攻击，实质上的方式就是有两个： ?? ??一， 迫使服务器的缓冲区满，不接收新的请求。 ?? ??二， 使用IP欺骗，迫使服务器把合法用户的连接复位，影响合法用户的连接 ?? ??这就是DOS攻击实施的基本思想。具体实现有这样的方法： ?? ??1、SYN FLOOD ?? ??利用服务器的连接缓冲区（Backlog Queue），利用特殊的程序，设置TCP的Header，向服务器端不断地成倍发送只有SYN标志的TCP连接请求。当服务器接收的时候，都认为是没有建立起来的连接请求，于是为这些请求建立会话，排到缓冲区队列中。 ?? ??如果你的SYN请求超过了服务器能容纳的限度，缓冲区队列满，那么服务器就不再接收新的请求了。其他合法用户的连接都被拒绝掉。可以持续你的SYN请求发送，直到缓冲区中都是你的只有SYN标记的请求。 ?? ??现在有很多实施SYN FLOOD的工具，呵呵，自己找去吧。 ?? ??2、IP欺骗DOS攻击 ?? ??这种攻击利用RST位来实现。假设现在有一个合法用户(1.1.1.1)已经同服务器建立了正常的连接，攻击者构造攻击的TCP数据，伪装自己的IP为1.1.1.1，并向服务器发送一个带有RST位的TCP数据段。服务器接收到这样的数据后，认为从1.1.1.1发送的连接有错误，就会清空缓冲区中建立好的连接。这时，如果合法用户1.1.1.1再发送合法数据，服务器就已经没有这样的连接了，该用户就必须从新开始建立连接。 ?? ??攻击时，伪造大量的IP地址，向目标发送RST数据，使服务器不对合法用户服务。 ?? ??3、 带宽DOS攻击 ?? ??如果你的连接带宽足够大而服务器又不是很大，你可以发送请求，来消耗服务器的缓冲区消耗服务器的带宽。这种攻击就是人多力量大了，配合上SYN一起实施DOS，威力巨大。不过是初级DOS攻击。呵呵。Ping白宫？？你发疯了啊！ ?? ??4、自身消耗的DOS攻击 ?? ??这是一种老式的攻击手法。说老式，是因为老式的系统有这样的自身BUG。比如Win95 (winsock v1), Cisco IOS v.10.x, 和其他过时的系统。 ?? ??这种DOS攻击就是把请求客户端IP和端口弄成主机的IP端口相同，发送给主机。使得主机给自己发送TCP请求和连接。这种主机的漏洞会很快把资源消耗光。直接导致当机。这中伪装对一些身份认证系统还是威胁巨大的。 ?? ??上面这些实施DOS攻击的手段最主要的就是构造需要的TCP数据，充分利用TCP协议。这些攻击方法都是建立在TCP基础上的。还有其他的DOS攻击手段。 5、塞满服务器的硬盘 ?? ??通常，如果服务器可以没有限制地执行写操作，那么都能成为塞满硬盘造成DOS攻击的途径，比如： ?? ??发送垃圾邮件。一般公司的服务器可能把邮件服务器和WEB服务器都放在一起。破坏者可以发送大量的垃圾邮件，这些邮件可能都塞在一个邮件队列中或者就是坏邮件队列中，直到邮箱被撑破或者把硬盘塞满。 ?? ??让日志记录满。入侵者可以构造大量的错误信息发送出来，服务器记录这些错误，可能就造成日志文件非常庞大，甚至会塞满硬盘。同时会让管理员痛苦地面对大量的日志，甚至就不能发现入侵者真正的入侵途径。 ?? ??向匿名FTP塞垃圾文件。这样也可以塞满硬盘空间。 ?? ??6、合理利用策略 ?? ??一般服务器都有关于帐户锁定的安全策略，比如，某个帐户连续3次登陆失败，那么这个帐号将被锁定。这点也可以被破坏者利用，他们伪装一个帐号去错误登陆，这样使得这个帐号被锁定，而正常的合法用户就不能使用这个帐号去登陆系统了。
DoS是英文“Denial of service”的缩写，中文意思是“拒绝服务”。DoS攻击专门设计用来阻止授权用户对系统以及系统数据进行访问，通常采用的攻击方式是让系统服务器超载或者让系统死机。类似于几百个人同时拨一个电话，导致电话繁忙和不可用。DoS攻击可能涉及到通过国际互联网发送大量的错误网络信息包。如果DoS攻击来源于单点进攻，那么可以采用简单的交通控制系统来探测到电脑黑客。较为复杂的DoS攻击可以包含多种结构和大量的攻击点。电脑黑客经常操纵其它计算机和网络服务器并且使用它们的地址进行DoS攻击，这样就可以掩盖他们自己的真实身份。 与之紧密相关的另一个概念就是DdoS ,DdoS是英文“distribution Denial of service”的缩写，中文意思是“分布式拒绝服务攻击”，这种攻击方法使用与普通的拒绝服务攻击同样的方法，但是发起攻击的源是多个。通常，攻击者使用下载的工具渗透无保护的主机，当获得该主机的适当的访问权限后，攻击者在主机中安装软件的服务或进程（以下简称代理）。这些代理保持睡眠状态，直到从它们的主控端得到指令。主控端命令代理对指定的目标发起拒绝服务攻击。随着 cable modems, DSL和危害力及强的黑客工具的广泛传播使用，有越来越多的可以被访问的主机。分布式拒绝服务攻击是指主控端可以同时对一个目标发起几千个攻击。单个的拒绝服务攻击的威力也许对带宽较宽的站点没有影响，而分布于全球的几千个攻击将会产生致命的效果 　　分布式拒绝服务攻击（DDoS）是目前黑客经常采用而难以防范的攻击手段。本文从概念开始详细介绍了这种攻击方式，着重描述了黑客是如何组织并发起的DDoS攻击，结合其中的Syn Flood实例，您可以对DDoS攻击有一个更形象的了解。最后作者结合自己的经验与国内网络安全的现况探讨了一些防御DDoS的实际手段。 　　DDoS攻击概念 　　　　 　　DoS的攻击方式有很多种，最基本的DoS攻击就是利用合理的服务请求来占用过多的服务资源，从而使合法用户无法得到服务的响应。 　　DDoS攻击手段是在传统的DoS攻击基础之上产生的一类攻击方式。单一的DoS攻击一般是采用一对一方式的，当攻击目标CPU速度低、内存小或者网络带宽小等等各项性能指标不高它的效果是明显的。随着计算机与网络技术的发展，计算机的处理能力迅速增长，内存大大增加，同时也出现了千兆级别的网络，这使得DoS攻击的困难程度加大了-目标对恶意攻击包的&消化能力&加强了不少，例如你的攻击软件每秒钟可以发送3,000个攻击包，但我的主机与网络带宽每秒钟可以处理10,000个攻击包，这样一来攻击就不会产生什么效果。 　　这时侯分布式的拒绝服务攻击手段（DDoS）就应运而生了。你理解了DoS攻击的话，它的原理就很简单。如果说计算机与网络的处理能力加大了10倍，用一台攻击机来攻击不再能起作用的话，攻击者使用10台攻击机同时攻击呢？用100台呢？DDoS就是利用更多的傀儡机来发起进攻，以比从前更大的规模来进攻受害者。 　　高速广泛连接的网络给大家带来了方便，也为DDoS攻击创造了极为有利的条件。在低速网络时代时，黑客占领攻击用的傀儡机时，总是会优先考虑离目标网络距离近的机器，因为经过路由器的跳数少，效果好。而现在电信骨干节点之间的连接都是以G为级别的，大城市之间更可以达到2.5G的连接，这使得攻击可以从更远的地方或者其他城市发起，攻击者的傀儡机位置可以在分布在更大的范围，选择起来更灵活了。 　　被DDoS攻击时的现象 被攻击主机上有大量等待的TCP连接 网络中充斥着大量的无用的数据包，源地址为假 制造高流量无用数据，造成网络拥塞，使受害主机无法正常和外界通讯 利用受害主机提供的服务或传输协议上的缺陷，反复高速的发出特定的服务请求，使受害主机无法及时处理所有正常请求 严重时会造成系统死机 　　攻击运行原理 一个比较完善的DDoS攻击体系分成四大部分，先来看一下最重要的第2和第3部分：它们分别用做控制和实际发起攻击。请注意控制机与攻击机的区别，对第4部分的受害者来说，DDoS的实际攻击包是从第3部分攻击傀儡机上发出的，第2部分的控制机只发布命令而不参与实际的攻击。对第2和第3部分计算机，黑客有控制权或者是部分的控制权，并把相应的DDoS程序上传到这些平台上，这些程序与正常的程序一样运行并等待来自黑客的指令，通常它还会利用各种手段隐藏自己不被别人发现。在平时，这些傀儡机器并没有什么异常，只是一旦黑客连接到它们进行控制，并发出指令的时候，攻击傀儡机就成为害人者去发起攻击了。 　　有的朋友也许会问道：&为什么黑客不直接去控制攻击傀儡机，而要从控制傀儡机上转一下呢？&。这就是导致DDoS攻击难以追查的原因之一了。做为攻击者的角度来说，肯定不愿意被捉到（我在小时候向别人家的鸡窝扔石头的时候也晓得在第一时间逃掉，呵呵），而攻击者使用的傀儡机越多，他实际上提供给受害者的分析依据就越多。在占领一台机器后，高水平的攻击者会首先做两件事：1. 考虑如何留好后门（我以后还要回来的哦）！2. 如何清理日志。这就是擦掉脚印，不让自己做的事被别人查觉到。比较不敬业的黑客会不管三七二十一把日志全都删掉，但这样的话网管员发现日志都没了就会知道有人干了坏事了，顶多无法再从日志发现是谁干的而已。相反，真正的好手会挑有关自己的日志项目删掉，让人看不到异常的情况。这样可以长时间地利用傀儡机。 　　但是在第3部分攻击傀儡机上清理日志实在是一项庞大的工程，即使在有很好的日志清理工具的帮助下，黑客也是对这个任务很头痛的。这就导致了有些攻击机弄得不是很干净，通过它上面的线索找到了控制它的上一级计算机，这上级的计算机如果是黑客自己的机器，那么他就会被揪出来了。但如果这是控制用的傀儡机的话，黑客自身还是安全的。控制傀儡机的数目相对很少，一般一台就可以控制几十台攻击机，清理一台计算机的日志对黑客来讲就轻松多了，这样从控制机再找到黑客的可能性也大大降低。 　　黑客是如何组织一次DDoS攻击的？ 　　　　 　　这里用&组织&这个词，是因为DDoS并不象入侵一台主机那样简单。一般来说，黑客进行DDoS攻击时会经过这样的步骤： 　　1. 搜集了解目标的情况 　　下列情况是黑客非常关心的情报： 被攻击目标主机数目、地址情况 目标主机的配置、性能 目标的带宽 　　对于DDoS攻击者来说，攻击互联网上的某个站点，如，有一个重点就是确定到底有多少台主机在支持这个站点，一个大的网站可能有很多台主机利用负载均衡技术提供同一个网站的www服务。以yahoo为例，一般会有下列地址都是提供http: //服务的： 　　66.218.71.87 　　66.218.71.88 　　66.218.71.89 　　66.218.71.80 　　66.218.71.81 　　66.218.71.83 　　66.218.71.84 　　66.218.71.86 　　如果要进行DDoS攻击的话，应该攻击哪一个地址呢？使66.218.71.87这台机器瘫掉，但其他的主机还是能向外提供www服务，所以想让别人访问不到的话，要所有这些IP地址的机器都瘫掉才行。在实际的应用中，一个IP地址往往还代表着数台机器：网站维护者使用了四层或七层交换机来做负载均衡，把对一个IP地址的访问以特定的算法分配到下属的每个主机上去。这时对于DDoS攻击者来说情况就更复杂了，他面对的任务可能是让几十台主机的服务都不正常。 　　所以说事先搜集情报对DDoS攻击者来说是非常重要的，这关系到使用多少台傀儡机才能达到效果的问题。简单地考虑一下，在相同的条件下，攻击同一站点的2台主机需要2台傀儡机的话，攻击5台主机可能就需要5台以上的傀儡机。有人说做攻击的傀儡机越多越好，不管你有多少台主机我都用尽量多的傀儡机来攻就是了，反正傀儡机超过了时候效果更好。
请登录后再发表评论!Posts - 610, Comments - 29744
这几天恰好和朋友谈起了递归，忽然发现不少朋友对于“尾递归”的概念比较模糊，网上搜索一番也没有发现讲解地完整详细的资料，于是写了这么一篇文章，权当一次互联网资料的补充。:P 递归与尾递归 关于递归操作，相信大家都已经不陌生。简单地说，一个函数直接或间接地调用自身，是为直接或间接递归。例如，我们可以使用递归来计算一个单向链表的长度：public class Node
public Node(int value, Node next)
this.Value =
this.Next =
public int Value { get; private set; }
public Node Next { get; private set; }
编写一个递归的GetLength方法：public static int GetLengthRecursively(Node head)
if (head == null) return 0;
return GetLengthRecursively(head.Next) + 1;
在调用时，GetLengthRecursively方法会不断调用自身，直至满足递归出口。对递归有些了解的朋友一定猜得到，如果单项链表十分长，那么上面这个方法就可能会遇到栈溢出，也就是抛出StackOverflowException。这是由于每个线程在执行代码时，都会分配一定尺寸的栈空间（Windows系统中为1M），每次方法调用时都会在栈里储存一定信息（如参数、局部变量、返回地址等等），这些信息再少也会占用一定空间，成千上万个此类空间累积起来，自然就超过线程的栈空间了。不过这个问题并非无解，我们只需把递归改成如下形式即可（在这篇文章里我们不考虑非递归的解法）：public static int GetLengthTailRecursively(Node head, int acc)
if (head == null) return
return GetLengthTailRecursively(head.Next, acc + 1);
GetLengthTailRecursively方法多了一个acc参数，acc的为accumulator（累加器）的缩写，它的功能是在递归调用时“积累”之前调用的结果，并将其传入下一次递归调用中——这就是GetLengthTailRecursively方法与GetLengthRecursively方法相比在递归方式上最大的区别：GetLengthRecursive方法在递归调用后还需要进行一次“+1”，而GetLengthTailRecursively的递归调用属于方法的最后一个操作。这就是所谓的“”。与普通递归相比，由于尾递归的调用处于方法的最后，因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义，因此完全可以把本次方法中留在堆栈中的数据完全清除，把空间让给最后的递归调用。这样的优化1便使得递归不会在调用堆栈上产生堆积，意味着即时是“无限”递归也不会让堆栈溢出。这便是尾递归的优势。
有些朋友可能已经想到了，尾递归的本质，其实是将递归方法中的需要的“所有状态”通过方法的参数传入下一次调用中。对于GetLengthTailRecursively方法，我们在调用时需要给出acc参数的初始值：GetLengthTailRecursively(head, 0)
为了进一步熟悉尾递归的使用方式，我们再用著名的“菲波纳锲”数列作为一个例子。传统的递归方式如下：public static int FibonacciRecursively(int n)
if (n & 2) return n;
return FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2);
而改造成尾递归，我们则需要提供两个累加器：public static int FibonacciTailRecursively(int n, int acc1, int acc2)
if (n == 0) return acc1;
return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);
于是在调用时，需要提供两个累加器的初始值：FibonacciTailRecursively(10, 0, 1)
尾递归与Continuation
，即为“完成某件事情”之后“还需要做的事情”。例如，在.NET中标准的APM调用方式，便是由BeginXXX方法和EndXXX方法构成，这其实便是一种Continuation：在完成了BeginXXX方法之后，还需要调用EndXXX方法。而这种做法，也可以体现在尾递归构造中。例如以下为阶乘方法的传统递归定义：public static int FactorialRecursively(int n)
if (n == 0) return 1;
return FactorialRecursively(n - 1) *
显然，这不是一个尾递归的方式，当然我们轻易将其转换为之前提到的尾递归调用方式。不过我们现在把它这样“理解”：每次计算n的阶乘时，其实是“先获取n - 1的阶乘”之后再“与n相乘并返回”，于是我们的FactorialRecursively方法可以改造成：public static int FactorialRecursively(int n)
return FactorialContinuation(n - 1, r =& n * r);
// 6. FactorialContinuation(n, x =& x)
public static int FactorialContinuation(int n, Func&int, int& continuation)
FactorialContinuation方法的含义是“计算n的阶乘，并将结果传入continuation方法，并返回其调用结果”。于是，很容易得出，FactorialContinuation方法自身便是一个递归调用：public static int FactorialContinuation(int n, Func&int, int& continuation)
return FactorialContinuation(n - 1,
r =& continuation(n * r));
FactorialContinuation方法的实现可以这样表述：“计算n的阶乘，并将结果传入continuation方法并返回”，也就是“计算n - 1的阶乘，并将结果与n相乘，再调用continuation方法”。为了实现“并将结果与n相乘，再调用continuation方法”这个逻辑，代码又构造了一个匿名方法，再次传入FactorialContinuation方法。当然，我们还需要为它补充递归的出口条件：public static int FactorialContinuation(int n, Func&int, int& continuation)
if (n == 0) return continuation(1);
return FactorialContinuation(n - 1,
r =& continuation(n * r));
很明显，FactorialContinuation实现了尾递归。如果要计算n的阶乘，我们需要如下调用FactorialContinuation方法，表示“计算10的阶乘，并将结果直接返回”：FactorialContinuation(10, x =& x)
再加深一下印象，大家是否能够理解以下计算“菲波纳锲”数列第n项值的写法？public static int FibonacciContinuation(int n, Func&int, int& continuation)
if (n & 2) return continuation(n);
return FibonacciContinuation(n - 1,
r1 =& FibonacciContinuation(n - 2,
r2 =& continuation(r1 + r2)));
在函数式编程中，此类调用方式便形成了“”。由于C#的Lambda表达式能够轻松构成一个匿名方法，我们也可以在C#中实现这样的调用方式。您可能会想——汗，何必搞得这么复杂，计算阶乘和“菲波纳锲”数列不是一下子就能转换成尾递归形式的吗？不过，您试试看以下的例子呢？
对二叉树进行先序遍历（pre-order traversal）是典型的递归操作，假设有如下TreeNode类：public class TreeNode
public TreeNode(int value, TreeNode left, TreeNode right)
this.Value =
this.Left =
this.Right =
public int Value { get; private set; }
public TreeNode Left { get; private set; }
public TreeNode Right { get; private set; }
于是我们来传统的先序遍历一下：public static void PreOrderTraversal(TreeNode root)
if (root == null) return;
Console.WriteLine(root.Value);
PreOrderTraversal(root.Left);
PreOrderTraversal(root.Right);
您能用“普通”的方式将它转换为尾递归调用吗？这里先后调用了两次PreOrderTraversal，这意味着必然有一次调用没法放在末尾。这时候便要利用到Continuation了：public static void PreOrderTraversal(TreeNode root, Action&TreeNode& continuation)
if (root == null)
continuation(null);
Console.WriteLine(root.Value);
PreOrderTraversal(root.Left,
left =& PreOrderTraversal(root.Right,
right =& continuation(right)));
我们现在把每次递归调用都作为代码的最后一次操作，把接下来的操作使用Continuation包装起来，这样就实现了尾递归，避免了堆栈数据的堆积。可见，虽然使用Continuation是一个略有些“诡异”的使用方式，但是在某些时候它也是必不可少的使用技巧。
Continuation的改进
看看刚才的先序遍历实现，您有没有发现一个有些奇怪的地方？PreOrderTraversal(root.Left,
left =& PreOrderTraversal(root.Right,
right =& continuation(right)));
关于最后一步，我们构造了一个匿名函数作为第二次PreOrderTraversal调用的Continuation，但是其内部直接调用了continuation参数——那么我们为什么不直接把它交给第二次调用呢？如下：PreOrderTraversal(root.Left,
left =& PreOrderTraversal(root.Right, continuation));
我们使用Continuation实现了尾递归，其实是把原本应该分配在栈上的信息丢到了托管堆上。每个匿名方法其实都是托管堆上的对象，虽然说这种生存周期短的对象不会对内存资源方面造成多大问题，但是尽可能减少此类对象，对于性能肯定是有帮助的。这里再举一个更为明显的例子，求二叉树的大小（Size）：public static int GetSize(TreeNode root, Func&int, int& continuation)
if (root == null) return continuation(0);
return GetSize(root.Left,
leftSize =& GetSize(root.Right,
rightSize =& continuation(leftSize + rightSize + 1)));
GetSize方法使用了Continuation，它的理解方法是“获取root的大小，再将结果传入continuation，并返回其调用结果”。我们可以将其进行改写，减少Continuation方法的构造次数：public static int GetSize2(TreeNode root, int acc, Func&int, int& continuation)
if (root == null) return continuation(acc);
return GetSize2(root.Left, acc,
accLeftSize =& GetSize2(root.Right, accLeftSize + 1, continuation));
GetSize2方法多了一个累加器参数，同时它的理解方式也有了变化：“将root的大小累加到acc上，再将结果传入continuation，并返回其调用结果”。也就是说GetSize2返回的其实是一个累加值，而并非是root参数的实际尺寸。当然，我们在调用时GetSize2时，只需将累加器置零便可：GetSize2(root, 0, x =& x)
不知您清楚了吗？
在命令式编程中，我们解决一些问题往往可以使用循环来代替递归，这样便不会因为数据规模造成堆栈溢出。但是在函数式编程中，要实现“循环”的唯一方法便是“递归”，因此尾递归和CPS对于函数式编程的意义非常重大。了解尾递归，对于编程思维也有很大帮助，因此大家不妨多加思考和练习，让这样的方式为自己所用。
尾递归与Continuation
注1：事实上，在C#中，即使您实现了尾递归，编译器（包括C#编译器及JIT）也不会进行优化，也就是说还是无法避免StackOverflowException。我会在不久之后单独讨论一下这方面问题。
Categories:
，登陆后便可删除或修改已发表的评论
（请注意保留评论内容）