二次元同好交流新大陆
扫码下载App
汇聚2000万达人的兴趣社区下载即送20张免费照片冲印
扫码下载App
温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！&&|&&
LOFTER精选
网易考拉推荐
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
阅读(2602)|
用微信&&“扫一扫”
将文章分享到朋友圈。
用易信&&“扫一扫”
将文章分享到朋友圈。
历史上的今天
loftPermalink:'',
id:'fks_',
blogTitle:'递归与循环的优缺点（转载）',
blogAbstract:'递归的话函数调用是有开销的，而且递归的次数受堆栈大小的限制。&以二叉树搜索为例：&bool search(btree* p, int v)&{&if (null == p)&&if (v == p-&v)&return true&else&{&if (v & p-&v)&return search(p-&left, v);&else&return search(p-&right, v);&}&}&如果这个二叉树很庞大，反复递归函数调用开销就很大，万一堆栈溢出怎么办？&现在我们用循环改写：&bool search(btree* p, int v)&',
blogTag:'',
blogUrl:'blog/static/',
isPublished:1,
istop:false,
modifyTime:9,
publishTime:8,
permalink:'blog/static/',
commentCount:2,
mainCommentCount:2,
recommendCount:0,
bsrk:-100,
publisherId:0,
recomBlogHome:false,
currentRecomBlog:false,
attachmentsFileIds:[],
groupInfo:{},
friendstatus:'none',
followstatus:'unFollow',
pubSucc:'',
visitorProvince:'',
visitorCity:'',
visitorNewUser:false,
postAddInfo:{},
mset:'000',
remindgoodnightblog:false,
isBlackVisitor:false,
isShowYodaoAd:false,
hostIntro:'',
hmcon:'1',
selfRecomBlogCount:'0',
lofter_single:''
{list a as x}
{if x.moveFrom=='wap'}
{elseif x.moveFrom=='iphone'}
{elseif x.moveFrom=='android'}
{elseif x.moveFrom=='mobile'}
${a.selfIntro|escape}{if great260}${suplement}{/if}
{list a as x}
推荐过这篇日志的人：
{list a as x}
{if !!b&&b.length>0}
他们还推荐了：
{list b as y}
转载记录：
{list d as x}
{list a as x}
{list a as x}
{list a as x}
{list a as x}
{if x_index>4}{break}{/if}
${fn2(x.publishTime,'yyyy-MM-dd HH:mm:ss')}
{list a as x}
{if !!(blogDetail.preBlogPermalink)}
{if !!(blogDetail.nextBlogPermalink)}
{list a as x}
{if defined('newslist')&&newslist.length>0}
{list newslist as x}
{if x_index>7}{break}{/if}
{list a as x}
{var first_option =}
{list x.voteDetailList as voteToOption}
{if voteToOption==1}
{if first_option==false},{/if}&&“${b[voteToOption_index]}”&&
{if (x.role!="-1") },“我是${c[x.role]}”&&{/if}
&&&&&&&&${fn1(x.voteTime)}
{if x.userName==''}{/if}
网易公司版权所有&&
{list x.l as y}
{if defined('wl')}
{list wl as x}{/list}C语言中的递归与死循环--blhlj的blog
时 间 记 忆
最 新 评 论
专 题 分 类
最 新 日 志
最 新 留 言
用 户 登 录
友 情 连 接
博 客 信 息
C语言中的递归与死循环
3:37:00 | By: blhlj ]
发表评论：第三章1 循环与递归_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
第三章1 循环与递归
上传于||暂无简介
大小：212.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢Posts - 610, Comments - 29711
在上文《》里，我们谈到了尾递归的概念和示例，不过有些朋友对于尾递归的功效依然有所怀疑。因此现在，我再简单讲解一下尾递归的优化原理，希望能给大家以一定理性认识。 尾递归的循环优化 尾递归，即是递归调用放在方法末尾的递归方式，如经典的阶乘：int FactorialTailRecursion(int n, int acc)
if (n == 0) return
return FactorialTailRecursion(n - 1, acc * n);
由于递归在方法的末尾，因此方法中的局部变量已经毫无用处，编译器完全可以将其“复用”，并把尾递归优化为“循环”方式：int FactorialLoopOptimized(int n, int acc)
while (true)
if (n == 0) return
不过，上文还提到了尾递归中的常用技巧Continuation。那么对于如下形式的Continuation，编译器又该如何优化呢？int FactorialContinuation(int n, Func&int, int& continuation)
if (n == 0) return continuation(1);
return FactorialContinuation(n - 1, r =& continuation(n * r));
我们先用“人脑”来思考一下，这段代码的执行方式是怎么样的。我们每次使用n和contn调用FactorialContinuation时，都会构造一个新的contn - 1，并同n - 1传入下一次FactorialContinuation调用中去。以此类推，直到n等于0时，就直接调用cont0并返回。至于每个Continuation的定义，我们可以归纳出如下结果：Func&int, 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
于是，我们可以根据这个“意图”，将FactorialContinuation方法“优化”为如下形式：int FactorialLoopOptimized2(int n, Func&int, int& continuation)
LinkedList&Func&int, int&& contList = new LinkedList&Func&int, int&&();
while (true)
if (n == 0) break;
int tempN =
Func&int, int& newCont = r =& tempN *
contList.AddFirst(newCont);
continuation = newC
return contList.Aggregate(1, (acc, cont) =& cont(acc));
我们构造了一个Continuation函数链表，随着n递减，每次都会把新的Continuation函数插入到链表头，最后Aggregate方法会将第一个参数（累加器）依次运用到每个函数中去，得到最后结果并返回。只可惜，这个优化完全是我们“一厢情愿”而已，这么做的前提是“理解”了函数的意义，把方法的迭代调用“拆开”，而编译器是无法（还是很难）帮我们优化到如斯地步的。那么编译器对于此类问题又该如何解决呢？
之前，我们使用C#中的匿名方法特性来构造每个Continuation方法。如果我们使用自定义的封装类，再将递归“优化”成循环，FactorialContinuation又会成为什么样呢？如下：private class Continuation
public Continuation(Func&int, int& cont, int n)
this.cont =
private Func&int, int&
private int n;
public int Invoke(int r)
return this.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).I
return continuation(1);
其实这才是FactorialContinuation的“直译”，也是编译器能够进行优化。不过朋友们应该也能够看出，这只是一个Continuation对象套着另一个Continuation对象。如果形成了数万个Continuation对象的嵌套，在最终调用最外层的Continuation时，每个内部的Continuation也会在调用时往同一个堆栈中不断累加，最终还是会造成堆栈溢出。因此，如果使用了Continuation，还是无法简单把递归优化成循环来避免堆栈溢出的。编译器还必须进行其他方面的优化。
方法尾调用的优化
上一篇文章曾经谈到：“与普通递归相比，由于尾递归的调用处于方法的最后，因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义，因此完全可以把本次方法中留在堆栈中的数据完全清除，把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积，意味着即时是“无限”递归也不会让堆栈溢出”。这其实才是尾递归的“正统”优化方式，那么我们先暂时忘记之前的“循环优化”，从最简单的示例中查看这样的优化是如何进行的。还是最简单的“尾递归”阶乘：static int FactorialTailRecursion(int n, int acc)
if (n == 0) return
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
// 返回递归调用结果
在这个问题上，我们还需要观察它的汇编代码（为了不干扰文章内容，我会把获取汇编代码的做法单独写一篇文章，稍后发布），如下：<font color="#ffd0
edx,[ecx-1]
ecx,[edx-1]
dword ptr ds:[703068h] (地址703068h的值即为<font color="#ffd0)
上面的汇编代码非常简单，从中可以看出，每次递归调用都使用了最简单的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
ecx,[eax-1]
eax,dword ptr ds:[813068h]
dword ptr [mscorwks!g_TrapReturningThreads (7204339c)],0
mscorwks!JIT_PollGC (71d5c9d3)
mscorwks!JIT_TailCall (71b02890)
在这里我实在无法完整讲述上述汇编代码的含义，不过从中可以看出它的确对于尾递归进行了特别的处理，而并非使用简单的call指令进行调用。对此互联网上的资源也不多，我只找到了，其中简单描述了Whidbey V2（真早）中CLR对于这方面的处理，以及一些相关的考虑，从中似乎能够看出一些苗头来。
让我们再回想之前的问题：Continuation无法通过简单优化为循环来解决递归问题。但是通过观察可以看出，Continuation.Invoke方法中的cont委托调用是最后一条命令，这说明它是一个“尾调用”——虽然不是“尾递归”，不过这已经满足tail指令的要求了：只需和所在方法返回值相同（或兼容）即可。因此，对于Continuation来说，我们也需要进行尾递归的优化。您可以进行尝试，现在无论递归多“深”，都不会使堆栈溢出了。
浅谈尾递归的优化方式
注1：与tail类似，IL指令jmp也能够用于方法调用。这两条指令都不会在调用栈上堆积数据。tail与jmp的不同之处在于，前者只需要返回值与所在方法相同或兼容即可，而后者需要签名完全相同。您可以想象得到，对于“直接递归”来说，可以使用jmp进行调用，而普通的“尾调用”，则只能使用tail了。
Categories:
，登陆后便可删除或修改已发表的评论
（请注意保留评论内容）