资源描述：
《深入理解递归函数》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、深入理解递归函数刚开始接触编程对递归调用都是比较头痛，很多年前我也会一样。昨天晩上睡觉突然想起了谭浩强C语言的汉诺塔递归调用，记得当吋是在高中的时候，我表姐在上大学，她把谭浩强的C语言给了我，只看书不实践，现在想起来效果还真差。其中递归调用汉诺塔看了好久都没有整明白，直到上大学学习C语言也还没有搞明白，当学到递归调用了，我就去问老师，老是说回去看看，下周告诉我。谁知到老师真的很忙，下周也没有结果。后来自己什么吋候明白的也忘记了。刚开始接触递归都会告诉你，递归占用资源，使程序复杂，最好不要使用；还有人说，如果这个人一来就是用递归，我肯
2、定不会聘用他。但是我认为这些观点太片面。递归算法的目的降低程序的复杂度，解放大脑负担，让大脑更加专注于问题本身。程序的性能跟递归没有什么关系，更重要的时算法本身，我们会在稍后讲解一下同i种算法同样是递归，性能的差异巨大。设计模式中，很多模式都存在递归。刚开始接触递归的，往往都会在里面打圈圈，自己越绕越晕，觉得递归太复杂。其实看待递归的时候，也是要分层面看待，不要把自己的大脑当做是电脑，可以绕很多的圈圈，有人说人的大脑同时能处理7个左右的变量，绕一圈就多几个变量，能绕几圈啊。呵呵。找到一个算法，在编写算法的吋候，只考虑一次递归所做的事
3、情，如果遇到到递归调用函数的时候，把他当做一个函数整体考虑，他能完成他要完成的事情，要相信他，也要相信自己。我们所在的层面就是算法的层面，或者一次执行的层面。如果在算法层面和递归调用层面来回穿插的思考，读懂递归算法将非常困难，递归的复杂度就在于压栈会导致大量的变量需要存储，对我们的大脑来说负担太重，但是对汁算机来说是小意思，相对来说算法层面往往很简单，所以我们一定要站在算法层面考虑问题，而不是递归层面。下面来看我如何一步一步实现汉诺塔：(VS2010C#控制台程序)[csharp]viewplaincopyprint^C1.clas
4、sProgram2・{3・staticvoidMain(string[]args)4.<6.7.8.9.staticvoidMove(intn»chara,charb，charc)10.{11.if(n<1)return;12.if(n==1)13・{14.MoveTo(a，c);15.}16.else17.{18•19.〃以下三句可能存在问题，只是为了快速思考，先写上，看着代码找感觉。20•Move(n-a,b,c);21.MoveTo(a^c);22.Move(n-1,a,b,c);23・}24.}25.25.privatest
5、aticvoidMoveTo(chara,charc)26.{27.thrownewNotlmplementedException();28.}29.}凭着感觉直接写了个Move方法，第一个参数为盘子的个数，将所有盘子从a移动到c°第一个判断，防止错误的参数。第二个判断，当n等于1时，也就是一个盘子，直接盘子从a移动到c上。如果多余一个，将个盘子从a移到b,再将最下面一个从a移动到c,最后从b上将n-1个盘子移动到c上。[csharp]viewplaincopyprint^Ch・〃这三句肯定有问题的，只是为了快速把人脑里的想法写出看
6、，看着来找感觉。1.Move(n・1,a,b,c);//这句要实现将A座n・l的盘子移动到B上。2.MoveTo(a,c);//这句实现将A座最下血的一个盘子移动到C上3.Move(n・1,a,b,c);//这句要实现将移动到B座的盘子在移动到C座上，这就OK了。因为Move这个方法就是要把盘子从a移动到c,所以我们在递归调用时仅仅记住这个函数的这个功能就行了，这是一个函数的整体功能。我们分别来讲解当N>1的3个步骤:第一步，讲个盘子从a移动到b。把盘子全部移动到b位置和c的方法是一样的，也就是算法是一样的。只是规模比原来少1。所以
7、我们可以递归调用Move方法来解决将个盘子从a移动到bo这吋b就像相当于原来的c位置了，那么就这样调用Move(n-1,a,c,b).第二步，当个盘子从a移动到bZ后，a上就一个盘子，我们就可以直接将盘子移动到c上面。调用MoveTo(a,c)实现盘子的移动。在这一步，其实就是相当于移动只有一个盘子的情况，我们还可以递归调算法本身Move(1,a,b,c);这样调用也是可以的。在执行完成后，a位置上是空的，b位置上有个盘子，c位置上有一个最大的盘子。第三步，在第二步之后，我们只需要将b位置上的盘子都移动到c位置就可以了。这个和第一步
8、类似，只是位置变了。b相当于原来的a位置(因为盘子在b上),a位置相当于原来的b位置，因为移动到c,所以c还是相当于与原来的c位置。语句调用这样写Move(n・1,b,a,c);完善MoveTo力法，输出结果就好了。如果是图形移动，在
