从10月3号到昨天,我们俱乐部历时5天的项目开发完成了. 这次集中开发基本上完成任务. 更增进了我们成员之间的感情. 整个过程让每个人感觉都很好. 大家齐心协力, 虽然遇到很多的困难, 但都很顺利的解决了. 同时我们也得到了来自于孙大烈老师, BILL哥的大力支持, 以及佟达的女朋友的理解. 在这里表示感谢.
具体的细节在这里不多说了。以后再整理吧。这些天可累坏了，先休息了。
对了，忘了说，我们做的是一个聊天工具，暂时定名为KIT。
[code:cpp]
if($test == 1)
{
return 0;
}[/code]
我一直在读研还是就业之间徘徊不定，原因是自己不知道读研与就业之间到底有什么差别，差别能有多大。这篇文章为我解答了疑惑，希望它也能给其它有同样的疑惑的朋友带来帮助。
另外，说一说我对本文的看法：本文通篇在谈的读研还是不读研的问题其实都是在围绕着“找工作”这个轴心在转，可是如果不想给别人打工呢？是读研还是不读？事实上很多大公司的老板们都没有研究生的学历，而那些高学历的高手们大多是他们的雇员。这虽不是绝对的，但值得我们思考。要自己干事业的朋友小心了，别被此文拐沟里去了。
如果你有实际开发工作经验，感觉自己的水平和实力进入了一个高原期，迫切需要从理论上提高，那么计算机学院是唯一选择。因为计算机学院才能让你在理论上更上一层楼。软件学院从教学计划上就没有把你往这方面带。当然能不能更上一层楼最终还是完全取决于你自己。需要特别说明的是，工作经验并不一定等于开发经验，我见过很多工作2-3年的人，但是没有一点开发经验。
你说：“他们都有很强的开发能力,只是不太喜欢读书,也只是希望混个学历对今后在岗位上晋升有好处”，我可以向你保证，你所说的人绝对不是开发能力很强的人。因为，1）高手不可能不喜欢读书；2）高手不可能想去混一个学历；3）高手不可能认为晋升是因为学历的原因。
还需要说明的是，考计算机的人未必个个都是高手，严格来说，大部分都不会编程序。也就是说，庸庸碌碌之辈仍然占绝大多数。研究生毕业的师兄只拿2500元左右的比比皆是，所以不要寄希望于拿一张研究生文凭出去赚高薪。但是，对于有实际开发工作经验的人，要想自己在3年之中有一个真正的提高的话，计算机学院提供了广阔的平台。就我所知，每一个月拿2万以上的也有（上海育碧，图形特效算法设计）。所以，同为研究生毕业，能力的差距是极大的。所以，不要去问“研究生毕业能拿多少？”，要问“像我这种水平的人，研究生毕业能拿多少钱？”这样人家才能够准确地回答你。
所谓“有实际开发工作经验”是指你目前已经具备下列能力：1）你已经认为C++和汇编语言都是很简单的语言，并能够自如地运用；2）你能够在30分钟之内想到正确的五子棋AI算法设计思路和方向；3）你完全理解STL为什么这么重要；4）你能够独立地解决所有的编译与链接问题，哪怕你从来没有遇到的问题，你也不需要询问任何人；5）英文网站是你的首要信息来源；6）能够读懂英语写成的国际标准，比如NTFS磁盘格式标准。7）你经常站在集合论的角度思考算法问题；8）能够理解一个简单的驱动程序，能够理解一个简单3D交互程序；9）你能够认识到线性代数和概率论在实际编程工作中的极端重要性；10）你完全理解COM的设计思想，尤其能够理解COM为什么要设计成这样；11）当我说到虚函数的重要作用时，你不会急着去找书来翻；12）你能够说出C++为什么比其他语言优秀的理由，记住这种理由应该来自于你的开发体会，而不是因为其他人都这么说。此外还有很多判断标准，但如果你同时具备5条以上，可以认为你已经具备相应的开发经验了。在这种状态下读研，你将取得读研效益的最大值。
读研最重要的是要明白你自己要干什么，不能等导师来告诉你你应该干什么。研究生的优势在于理论功底深厚，思维具有穿透力，当然编程能力首先要过关，不要读完研究生还不知道MFC程序的WinMain函数在哪里。所以，研究生期间，你一定要做有理论深度的算法设计，比如大规模数据的搜索算法，性能是首要考虑因素，不要奢望SQL函数能够帮你解决问题，所有的问题你都必须自己解决，你必须解决内外存交换的性能瓶颈。再比如极品飞车的3D场景生成，图形变换，碰撞检测，物性模拟，纹理映射，灯光模型等等，这些都是可以保证你能拿到2万以上月薪的技术。如果你认为这些东西太难，不可能做得出来的话，那么你就不适合读研。真的，要是你认为读研之后还是要去搞一般的程序设计，如信息管理系统之类的软件，那么你读研的价值就完全不会得到体现，因为这些工作根本就不需要读研。
软件学院宣称培养软件开发人才，恕我直言，我从来没有看见那个高手是培训成功的。成为软件开发高手的路只有一条：自学！软件开发中需要大量的编程实践和独立思考，只有在此过程中，你才能够逐步成长起来。软件学院宣称培养软件项目经理，这更是搞笑，在某种意义上这是欺骗行为。学院里面能够培养出软件开发经理更是十足的谎言，软件项目经理必须，或者说更强调从战争中学会战争。没有实践经验的项目经理就是绣花枕头一个。
实话实说，软件学院就是一个蒙钱的机构，公关工作做得很好，善于打广告，而且都是打着高薪的幌子，就如同外面的什么北大青鸟培训班一样。两个字：蒙钱！四个字：还是蒙钱！
总之一句话，如果你只想成为软件开发高手（比如认为会编驱动程序或杀毒软件就是高手的那种），建议工作，不要考研；完全没有工作经验的，也不建议考研，你进来了只有瞎混一通。如果你有上述工作经验且想成为高级软件工程师（能够独立理解并设计出快速傅立叶变换算法的那种软件工程师）的话，那么强烈建议考研。考研让你有3年放松思考的机会，也有3年让你思想和技术积累沉淀的机会。非常难得的机会。不考研的话，这种机会就是一种奢侈，可望而不可即的那么一种奢侈。
所以，不管你是哪一种情况，都不建议考软件学院。除非你是女生，把能够成为一个研究生当着一生最大满足的那种女生。
1）关于读书的机会成本问题。读研的机会成本的确是很高。任何人都可以简单地计算出来。所以，我也不赞成所有的人都去读研。读研只适合那些痛感数学在编程中的极端重要性的人。如果对理论工具和理论思维的极端重要性没有切肤的认识，那么读研的价值几乎为0；读研的好处在于：A，把你自己放在一个学术和工程的交叉点上；B，让你具备了进入微软等世界顶级软件研发机构的可能性；记住只是可能性。但是不读研这种可能性为0；C，如前所述，如果没有读研的机会，你也就没有静下心来好好钻研几年理论的机会；一边工作拿高薪，一边深入地学习各种理论，诸位认为这可能吗？我反正认为不可能，我觉得学习钻研理论最需要的就是一个长期安静独处的环境，一边工作一边读书是不可能有这样的环境的，你会觉得每天都在疲于奔命。而读研正好可以提供这样一个环境。我同时还反对整天跟着导师的屁股后面跑，这样会浪费很多时间。读计算机的研究生，主要依靠自己去查阅最新文献，自己去研读文献，和导师的口头交流一个月一次就足够了，前提还需要导师的水平足够牛。如果导师的水平不牛，这也没关系，不理他就是了，自己做好自己的事情即可。
2）关于研究生教学质量问题。坦白地说，全国都是“洪桐县中无好人”，尤其在计算科学领域，大牛极少。那为什么还要去读研？大哉问！把读研的收获寄托在名校或名师的名我认为气上，是注定要失败的。读研全靠自学，研究生之间的差距全部体现在自学能力上面。又有人问，既然是自学，为什么非要读研？回答是：因为读研就是为你买一份保险，就是买一份你自学三年之后不会失业的保险。这份保险主要是一种心理上的后盾，让你在自学过程中经得起诱惑，能够从容镇定地去追寻计算机理论发展的坚实足迹，从欧拉，费马，高斯，康托，图灵等巨匠那里寻找方法论的珠宝。倘若没有这份保证，你在家里面自学3个月，保证你会被失业的压力压得喘不过气来，何谈安心学习？
3）关于实战经验与理论学习的优劣问题。这没有定论，如前所述，管理信息系统，设备驱动开发，工具软件开发，软件病毒剖析等等这些工作不太需要创造性，需要的是耐心和经验，需要的是对既有规范的准确理解，这类开发工作最适合在实战中提高，理论学习没什么作用。但是在人工智能，模式识别，图像压缩，虚拟现实，巨量数据检索，自然语言理解，计算机图形学等等领域，理论学习就占据着绝对的统治地位！这些领域的突破对人类的生活的影响是极其巨大而深刻的。某些领域处于一个极其快速发展的态势之中，比如计算机图形学，相信诸君能够从众多3D游戏的灿烂辉煌中体认到我的这种说法。在这些领域，如果没有扎实的理论功底，一切都是那么遥远，不管你花了多少时间在编程上面。
4）关于高级研发人员的知识结构问题。首先声明，我不是一个纯粹理论激进分子，即认为除了理论之外，一切都不重要。我认为，纯熟的编程技能是最基本但也是最必不可少的技能。没有这个基础，一切计算机理论就是空谈（研究图灵可计算性理论的研究者除外）。有了这个基础之后，下列理论学习方向必须重点突破：
1，科学哲学。这是核心中的核心！可惜国内不开这门课。不但不开课，而且还作为批判对象来引用，实在是遗憾至极！这是一门教你如何“钓鱼”的学科，在一切科学研究中居于最核心的地位。它是古今科研方法和思维方法的集大成者，很难想象一个成熟的研究者没有一套自己的方法论体系。科学哲学最需要的是领会与总结，它的思想与启示会伴随我们的一生。
2，康托集合论，矩阵方法，离散结构，图论方法，群论方法之间的紧密关系。最重要的认识这些理论对实践的重要启示和方法引导。我始终认为，如果你学了一门理论之后，却不知道这门理论有什么作用，那么你的理论就白学了，你什么东西都没有捞着。所以，学习任何理论之前，先问自己：它有什么用？在哪里用？如何用？带着这些问题去学习理论，你才会真正地学到东西。用这三个问题去问你的理论课老师，他的回答就是判断其实际水平的最佳标准。
3，思维要有极强的穿透力，学会看透文献作者没有写出来的动机。绝大部分大师都有隐瞒自己最具有方法论启示意义的思考环节的习惯。牛顿和华罗庚先生都有这个坏习惯。这让大家认为他们是天才，因为很多问题他想到了，我们想不到。但是为什么他们能想到，我们想不到？他们是怎样想到的？没有人告诉我们牛顿发现万有引力定律时的思考过程，当然，牛顿可以慷慨地把他的思考结果告诉我们，但是，他那可以点石成金的“金手指”却没有教给我们。我们的任务就是要培养透过文章看穿作者背后意图和动机的能力，在这方面，台湾的侯捷和美国的Donbox是绝佳典范。这两只老狐狸（呵呵，是爱称）凭着其猎犬一般的嗅觉，抽丝剥茧，一个把COM背后的幕后设计动机揭开并暴露到了光天化日之下，另一个把MFC的宏观架构做了一次完美的外科手术。其非凡的思维穿透力令人惊叹。
4，英语。英语本身不重要，但是用英语写成的文献就极其重要了。所以，专门把英语作为一个重头??搞计算机的而言，英语就是你的母语！
5，其它的具体理论还有很多，但是都不如这三个方面重要，因为我觉得这三个方面是最具有根本性，全局性的能力培养环节。需要指出的是，很多高深理论对你的工作是无意义的，当心时间陷进去。一定要把效率最高的时间段用在最具有决定性意义的理论学习上。
5）关于读研之后的出路是否光明的问题。我们应该承认，读研之后，你的工作机会不是变多了，而是变少了。而且越是高手，他的工作机会和工作范围就越少。这是因为，越是搞前沿研发的公司，其数量越少，在这个圈子的人也就越少。你找工作的范围就越小，试问：如果微软的OS设计专家出来找工作，能够让他选择的公司能有几家？但是，这种公司数量的减少是以工资待遇的急剧上升为补偿的，同时，你在工作中所受到的充分尊重也是在一般公司中体会不到的。所以不要担心学了高科技用不上，呵呵，你只会越来越感觉自己学的不够用。相信接到过猎头公司电话的人会体会得到。真正的高手从来就不会担心工作的问题，也从来不会到人才市场上去找工作。既然选择了理论深入，那么就应该把眼光放得更远
最近在和几个同学重温Shell编程。上一次学的时候只学了个皮毛，没怎么深入，这回准备好好的学习一下。这个学习心得不对Shell编程的基础进行详细的讲解，只对我们在学习中遇到的一些问题、解决方法及学习心得做必要的阐述，同时，我也希望能在讨论Shell编程的同时，把它做为一个接口，去学习一些Unix/Linux内部的一些更深入的内容。
这篇文章先发几个我们在讨论中遇到的问题：
1、Linux下的文件和目录都有很严格的权限设定，比如读权限，写权限，执行权限等。这些权限的含义都很容易理解，如果有读权限就可以读该文件，如果有可写权限就可以写该文件，同样，如果有执行权限就可以执行该文件。不过对于执行权限我却有一个问题，那就是，对于目录来说，执行权限的含义是什么？经过实践，发现如果对一个目录没有执行权限，那么就不能使用cd命令切换到该目录，但如果同时有读权限的话，是可以用ls把目录中的内容读取出来的。那么，这种现象说明了什么呢？系统内部对于目录的可执行权限是如何解释的呢？不太明白。同时还注意到，cd是一个shell内部命令，而ls是一个外部命令，不知道这个不同与此现象是否有关。此为问题一。
2、Linux下的文件和目录是通过inode来管理的，它们的权限、存储位置都是存放在inode中的。每个文件系统都有一个专门的inode区域，用于存放inode，每一个inode对应于一个文件或者目录。inode的大小是固定的，其作用相当于指针，指向数据区中的文件内容。当我们讨论硬链接的时候发现一个问题，书上说（《鸟哥的私房菜：基础篇》）目录只消耗inode，而不消耗数据区空间，所以不能用硬链接指向目录，那么问题就来了，目录中的信息是保存在哪的呢？我们知道，目录中记录了inode编号和文件名的对应关系，且目录中可能有很多条这样的记录，对记录的规模好像没有限制，而inode的大小是有限的，如果目录中记录的规模超出的inode的大小，那么多出来的信息保存在哪里呢？目录是怎么做到不消耗数据区的呢？此为问题二。
3、Linux启动时只有一个init进程，其它的进程都是由它或者它的子进程fork出来的，而init进程的所有者是root，而系统中运行的其它进程可以属于其它用户，那么当一个进程进行了fork操作之后，在它的子进程中用exec运行另一个进程，这个新的进程的所有者是否可以改变呢？比如我以用户root的身份运行一个进程，并在这个进程中调用了fork，然后在子进程中运行另一个程序，那么我是否可以把子进程的所有者改为我系统上的另一个用户dzy呢？如果可以，系统内部是如何实现的？
本文只提问题，不做回答（因为还没有回答），希望能与大家探讨。
最近在看一本书：《自己动手写操作系统》。虽然看了没多少，但只是此书的前言就已经吸引了我，使我不得不把这本书读完。我很赞同作者对于如何学好计算机科学的看法：边实践、边学习。我也认为人不可能把所有理论都学过之后才能去实践，因为那样的话不但浪费很多的时间，而且一旦实践起来会遇到很多问题，而这些问题是我们从理论的书本上无法学到的。这些困难很有可能让缺少实践的新手望而却步。而边实践边学习就可以随时知道自己欠缺的知识有哪些，学习的方向容易明确，而且在不断的实践中，不断的获得成就感，更有助于进步。
暑假的时候可能会尝试着自己写一个操作系统，虽然对此知道的并不多，但还是要试试，学习为主。不求完美，但求有所收获。
最近在做网站，不过做来做去感觉没有太多的收获。前几天和孙老师聊天，我就问了一下做网站对于学计算机科学有什么帮助。孙老师说帮助肯定有，而且还不小，只是看你怎么做。如果做内容型的网站，那就与计算机科学没什么关系了，如果做像Google那样的网站，那对于学计算机科学的帮助就会很大。我又问WEB的作用到底是什么。孙老师说，如果你有一个很好的技术想把它展示出来，就要用到WEB了。
其实在我理解，WEB技术是一个工具，真正的计算机科学还在后台。学计算机科学，绝不是做做网站，写两个全站程序那么简单的事情。这些东西谁都能做。对于从事计算机科学的人来说，核心的问题还是如何使计算机解决更多的问题，如何让计算机的解题效率更高。说来说去就是对于计算机底层的了解和对于算法的研究。此为内功，而做网站、编程序这一类的技能，是为外功。从事计算机的，也就像走江湖的，有内家的高手，有外家的名流。但最牛的还是内外兼修的高人。说具体点，那些搞基础理论研究的就是内家的高手了，这些人的特点是每天都在与数学打交道；那些高工程的就是外家的名流了，他们主要是与代码打交道；内外兼修的，比较少见，主要是一些大牛。
我这个无名小卒，近期想练好外家拳法，再好好练练内功，争取内外兼修。咱也做做高手梦。
前天下午，我和于墨写的报告被审阅了。然后我们被叫去“面谈”。跟我们谈话的是实验室主管硬件的杨老师，首先一上来杨老师就问我们：“你们怎么知道实验室用的是HUB？”。语气颇为严厉。我和于墨蒙了，没想到老师这么直接了当。在我们写报告前我们问了一个师兄关于实验室网络的连接情况，然后师兄说用的是HUB，我们就按照HUB写了。结果不对。。。
接着杨老师又问我们，实验室的网关是一台什么样的机器？CPU主频多少？机器内存多大？网关是通过哪里连接到互联网的？实验室内部网络是如何连接的？IP如何分布的？网关的负载有多大？它的现在的负载是多少？是否超过负载？
不用说，我们一个也回答不上来。接着杨老师强调了“严谨”的问题，告诉我们无论做什么都要严谨，要对自己说过的话负责。比如HUB还是交换机的问题，只要看一眼就知道了。很简单。不能人云亦云。
杨老师说了很多。对我的启发很大。做技术工作的确需要严谨的工作态度，像我们这样没有实地考察就擅自做出判断是在是很低级的错误，也是不负责任的错误。以前说“听君一席话，胜读十年书”感觉还不是很明显，这次真的有这样一种感觉。
以后可要好好培养自己严谨的态度。不能再马马虎虎的让人笑话了。
前几天我们在讨论递归的过程中发现，递归在解决某些问题的时候使得我们思考的方式得以简化，代码也更加精炼，容易阅读。那么既然递归有这么多的优点，我们是不是什么问题都要用递归来解决呢？难道递归就没有缺点吗？今天我们就来讨论一下递归的不足之处。
我们知道，递归调用实际上是函数自己在调用自己，而函数的调用开销是很大的，系统要为每次函数调用分配存储空间，并将调用点压栈予以记录。而在函数调用结束后，还要释放空间，弹栈恢复断点。所以说，函数调用不仅浪费空间，还浪费时间。
这样，我们发现，同一个问题，如果递归解决方案的复杂度不明显优于其它解决方案的话，那么使用递归是不划算的。因为它的很多时间浪费在对函数调用的处理上。在C++中引入了内联函数的概念，其实就是为了避免简单函数内部语句的执行时间小于函数调用的时间而造成效率降低的情况出现。在这里也是一个道理，如果过多的时间用于了函数调用的处理，那么效率显然高不起来。
举例来说，对于求阶乘的函数来说，其迭代算法的时间复杂度为O(n)：
而其递归函数的时间复杂度也是O(n)：
但是递归算法要进行n次函数调用，而迭代算法则只需要进行n次迭代而已。其效率上的差异是很显著的。
我们再来看看之前我们讨论的费波纳契数列问题。
我们当时使用的是简单的用定义来求 fib(n)，也就是使用公式 fib(n) = fib(n-1) + fib(n-2)。这样的想法是很容易想到的，可是仔细分析一下我们发现，当调用fib(n-1)的时候，还要调用fib(n-2)，也就是说fib(n-2)调用了两次，同样的道理，调用f(n-2)时f(n-3)也调用了两次，而这些冗余的调用是完全没有必要的。可以计算这个算法的复杂度是指数级的。
那么计算费波纳契数列是否有更好的递归算法呢？ 当然有。让我们来观察一下费波纳契数列的前几项：
1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …
注意到没有，如果我们去掉前面一项，得到的数列依然满足f(n) = f(n-1) – f(n-2), (n>2)，而我们得到的数列是以1，2开头的。很容易发现这个数列的第n-1项就是原数列的第n项。怎么样，知道我们该怎么设计算法了吧？我们可以写这样的一个函数，它接受三个参数，前两个是数列的开头两项，第三个是我们想求的以前两个参数开头的数列的第几项。
在函数内部我们先检查n的值，如果n为3则我们只需返回a+b即可，这是简单情境。如果n>3，那么我们就调用f(b, a+b, n-1)，这样我们就缩小了问题的规模（从求第n项变成求第n-1项）。好了，最终代码如下：
这样得到的算法复杂度是O(n)的。已经是线性的了。它的效率已经可以与迭代算法的效率相比了，但由于还是要反复的进行函数调用，还是不够经济。
由以上分析我们可以看到，递归在处理问题时要反复调用函数，这增大了它的空间和时间开销，所以在使用迭代可以很容易解决的问题中，使用递归虽然可以简化思维过程，但效率上并不合算。效率和开销问题是递归最大的缺点。
虽然有这样的缺点，但是递归的力量仍然是巨大而不可忽视的，因为有些问题使用迭代算法是很难甚至无法解决的（比如汉诺塔问题）。这时递归的作用就显示出来了。
递归的效率问题暂时讨论到这里。
昨天说了一些递归的简单应用，今天再说一点其他的应用吧。
不得不提的一个经典的问题是汉诺塔问题。问题是这样的：
有三个柱子，其中的一个上面套着八个圆盘，从下到上，圆盘按从大到小的顺序排列。要求把所有圆盘移动到另一个柱子上，并遵循以下规则：
- 一次只能移动一个圆盘
- 圆盘只能套在柱子上
- 小圆盘只能放在比它大的圆盘上
要解决这个问题，用普通的方法来作实在是很困难。而用递归来解决呢？ 会不会有一个容易的解决方案呢？
还是考虑递归的两个条件，是否可把问题规模缩小，是否存在简单情境。为了便于讨论，我们把圆盘现在所在的柱子称为源，把圆盘要移动到的柱子成为目的，另外一个柱子称为辅助。我们容易发现，要把最大的圆盘移动到目的，首先要把上面较小的七个圆盘移动到辅助上（注意，这是一个与原问题有着相同的形式且规模更小的问题），然后把大圆盘移动到目的上，在把七个较小圆盘从辅助移动到目的。可以看到，移动七个小圆盘其实与原问题形式相同而规模更小。好了，我们已经成功地缩小了问题规模。下面来找找简单情境。
很容易看到，当只有一个圆盘时，只要把它从源移动到目的就行了。这就是简单情境。
好，两个条件都具备了，我们可以开始写程序了。
以上就是实现输出汉诺塔问题解的主要函数了。你可以编写一个主程序来调用它们。像这样：
不错吧，很简洁的，几行代码，就解决了这个问题。是不是很爽呢？不过这个递归调用的算法的复杂性如何呢？让我们来看看。
记规模为n的输入耗时T(n)，则：
[tex]T(1) = 1[/tex]
[tex]T(n) = 2*T(n-1) + 1[/tex]
[tex]T(n) + 1= 2*(T(n-1) + 1)[/tex]
[tex]T(n) + 1 = (T(1) + 1) * ( 1 – (T(1)+1)^n) / ( 1 – (T(1)+1))[/tex]
[tex]T(n) = 2^n – 1[/tex]
啊，指数级，好像效率不太高啊。但确实解决了问题。
这是一个很经典的例子，我们来给它改个版，留为今天的作业吧：
所有要求不变，添加如下要求：
圆盘不能从源直接移动到目的。
如何解决此问题？复杂度是多少？
昨天大体上说了一下递归的根本思想和使用递归解决问题的两个条件。今天来看看在解决具体问题的时候如何使用递归。
探测回文：
回文是一种字符串，它正着读和反着读都是一样的。比如level,eye都是回文。用迭代的方法可以很快地判断一个字符串是否为回文。用递归的方法如何来实现呢？
首先我们要考虑使用递归的两个条件：
第一：这个问题是否可以分解为形式相同但规模更小的问题？
第二：如果存在这样一种分解，那么这种分解是否存在一种简单情境？
先来看第一点，是否存在一种符合条件的分解。容易发现，如果一个字符串是回文，那么在它的内部一定存在着更小的回文。 比如level里面的eve也是回文。 而且，我们注意到，一个回文的第一个字符和最后一个字符一定是相同的。所以我们很自然的有这样的方法：先判断给定字符串的首尾字符是否相等，若相等，则判断去掉首尾字符后的字符串是否为回文，若不相等，则该字符串不是回文。 注意，我们已经成功地把问题的规模缩小了，去掉首尾字符的字符串当然比原字符串小。
接着再来看第二点， 这种分解是否存在一种简单情境呢？简单情境在使用递归的时候是必须的，否则你的递归程序可能会进入无止境的调用。对于回文问题，我们容易发现，一个只有一个字符的字符串一定是回文，所以，只有一个字符是一个简单情境，但它不是唯一的简单情境，因为空字符串也是回文。这样，我们就得到了回文问题的两个简单情境：字符数为1和字符数为0。
好了，两个条件都满足了，基于以上分析，我们可以很容易的编写出解决回文问题的递归实现方式：
看起来很不错嘛。只有简单的几行代码，非常的简短，就解决了问题。
还有一个典型的例子是对已排序数组的二分查找算法。
现在有一个已经排序好的数组，要在这个数组中查找一个元素，以确定它是否在这个数组中，很一般的想法是顺序检查每个元素，看它是否与待查找元素相同。这个方法很容易想到，但它的效率不能让人满意，它的复杂度是O(n)的。现在我们来看看递归在这里能不能更有效。
还是考虑上面的两个条件：
第一：这个问题是否可以分解为形式相同但规模更小的问题？
第二：如果存在这样一种分解，那么这种分解是否存在一种简单情境？
考虑条件一：我们可以这样想，如果想把问题的规模缩小，我们应该做什么？可以的做法是：我们先确定数组中的某些元素与待查元素不同，然后再在剩下的元素中查找，这样就缩小了问题的规模。那么如何确定数组中的某些元素与待查元素不同呢？ 考虑到我们的数组是已经排序的，我们可以通过比较数组的中值元素和待查元素来确定待查元素是在数组的前半段还是后半段。这样我们就得到了一种把问题规模缩小的方法。
接着考虑条件二：简单情境是什么呢？ 容易发现，如果中值元素和待查元素相等，就可以确定待查元素是否在数组中了，这是一种简单情境，那么它是不是唯一的简单情境呢？ 考虑元素始终不与中值元素相等，那么我们最终可能得到了一个无法再分的小规模的数组，它只有一个元素，那么我们就可以通过比较这个元素和待查元素来确定最后的结果。这也是一种简单情境。
好了，基于以上的分析，我们发现这个问题可以用递归来解决，二分法的代码如下：
这个算法的复杂度是O(logn)的，显然要优于先前提到的朴素的顺序查找法。
好了，今天就说到这里，光看不管用，不如留个练习题您回去做做：
写一个函数dig_sum(int n)，输入一个非负整数，返回组成它的数字之和。如：dig_sum(2007) = 2+0+0+7 = 9。
学C语言的时候老师说递归挺难的，但也是很好用的，同时还是一个合格的程序员必须要掌握的。
从学编程以来对递归的理解就不太深刻。一直就停留在“自己调用自己”的程度上。这其实这只是递归的表象（严格来说连表象都概括得不全面，因为除了“自己调用自己”的递归外，还有交互调用的递归）。而递归的思想远不止这么简单。前些日子看了一本叫《程序设计抽象思想》的书，里面很详细的论述了递归的思想。看后令我颇受启发。所以，我开始写这个关于递归的系列，希望能与同道们一同探讨一下递归的力量。
递归，并不是简单的“自己调用自己”，也不是简单的“交互调用”。它是一种分析和解决问题的方法和思想。简单来说，递归的思想就是：把问题分解成为规模更小的、具有与原问题有着相同解法的问题。比如二分查找算法，就是不断地把问题的规模变小（变成原问题的一半），而新问题与原问题有着相同的解法。
有些问题使用传统的迭代算法是很难求解甚至无解的，而使用递归却可以很容易的解决。比如汉诺塔问题。但递归的使用也是有它的劣势的，因为它要进行多层函数调用，所以会消耗很多堆栈空间和函数调用时间。
既然递归的思想是把问题分解成为规模更小且与原问题有着相同解法的问题，那么是不是这样的问题都能用递归来解决呢？答案是否定的。并不是所有问题都能用递归来解决。那么什么样的问题可以用递归来解决呢？一般来讲，能用递归来解决的问题必须满足两个条件：
如果一个问题不满足以上两个条件，那么它就不能用递归来解决。
举个例子：
求费波纳契数列的第N项的值。
这是一个经典的问题，说到递归一定要提到这个问题。费波纳契数列这样定义：
f(0) = 0, f(1) = 1, 对n > 1, f(n) = f(n-1) + f(n-2)
这是一个明显的可以用递归解决的问题。让我们来看看它是如何满足递归的两个条件的：
1、对于一个n>2, 求f(n)只需求出f(n-1)和f(n-2)，也就是说规模为n的问题，转化成了规模更小的问题；
2、对于n=0和n=1，存在着简单情境：f(0) = 0, f(1) = 1。
因此，我们可以很容易的写出计算费波纳契数列的第n项的递归程序：
[c]int fib(n){
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return f(n-1) + f(n-2);
}[/c]
注意：在编写递归调用的函数的时候，一定要把对简单情境的判断写在最前面，以保证函数调用在检查到简单情境的时候能够及时地中止递归，否则，你的函数可能会永不停息的在那里递归调用，你就成了造出第一个永动机的人了。
（未完待续
Page optimized by WP Minify WordPress Plugin
段 志岩