秒懂汉诺塔原理函数递归
想当年大一刚学C语言递归那一块儿的时候，遇到了“汉诺塔”问题，我的老天，那段时期想哭好吗，深刻的打击了我的编程热情，本身我就自觉智商不高，于是一直就没搞懂过这个问题，指导最近看了《JavaScript语言精粹》，才发现递归并没有那么难。。。我之前对于递归的了解只限于一个函数调用它自身，所以一直懵懵懂懂，现在需要重新认识一下它：
递归函数是干啥用的
递归函数就是会直接或间接调用自身的一种函数。它把一个问题分解为一组相似的子问题，每一个都用一个寻常解去解决。也就是说，递归用一般的方式去解决每个子问题。
汉诺塔是什么
因为这是篇笔记，相信每个想了解汉诺塔原理的人都懂它是什么，怎么玩，但是就算你会玩，你不会写代码(大佬除外)。。。我就是从这个时候觉得自己智商比别人低的，不过这是我刚接触编程的时候。到现在接触了两三年的编程，我深感周围大佬没多少(可能因为我双非一本非计算机专业的缘故)，当初那些一看就会的人大部分接触的早O__O，人家初中高中奥数什么的早就接触啦，对于我们这种普通学生来说(我相信你要是985,211不会来看我的博客的)，大部分像我这样的人(为了不让大佬们黑我)都是学以致用的，参考别人的摸出门路了才会用，所以接下来我写的，应该都能懂。
汉诺塔递归代码
有时搜一篇资料，先看到源码，哇看不懂，再看原理，哇更不懂；也可能先看到原理，没代码我怎么会看懂，再看源码，哇原理我都看不懂看代码怎么会懂。。。所以这就陷入了死循环，至于能不能看懂，就看个人的喜好和悟性了，我的习惯是先看源码。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16<pre>
<script type="text/javascript">
var hanoi=function(n,src,aux,dst){
if(disc>0){
//第一步
hanoi(n-1,src,dst,aux);
//第二步
document.writeln("Move disc "+n+" from "+src+" to "+dst);
//第三步
hanoi(n-1,aux,src,dst);
}
};
hanoi(3,"Src","Aux","Dst");
hanoi(4,"Src","Aux","Dst");
</script>
</pre>
汉诺塔递归原理
你可以发现它看上去非常的简单，一共就三步，毕竟hanoi函数就是把一堆圆盘从一根柱子移到另一根柱子，必要时使用辅助的柱子。函数的参数解释如下：
1.n是一开始由小到大排在src柱子上的圆盘数量
2.src代表起始柱子
3.aux(auxiliary)代表辅助柱子
4.dst(destination)代表目标柱子
hanoi函数把问题分解为了三个子问题，
第一步：它移动n-1个较小的圆盘到辅助柱子上，从而露出下面最大的圆盘。
第二步：移动下面最大的圆盘到目标柱子上。
第三步：将刚才较小的圆盘从辅助柱子上再移动到目标柱子上。
然后通过递归地调用自身(只是参数不同)去处理一对圆盘的移动，从而解决那些子问题。
对递归原理的理解
hanoi(3,”Src”,”Aux”,”Dst”);代表把3个圆盘从Src柱子借助Aux柱子移动到Dst柱子。每一个大问题里包含三个子问题:如果起始柱子上有盘子，先把disc-1个较小的圆盘都放到辅助柱子上，然后把较大的放到目标柱子上，最后在把那disc-1个较小的圆盘放到目标柱子上。
相信读到这里的人都搞懂了怎么把这个大问题分解为3个子问题，并且发现如果按着原理思路来写，即可写出代码。但是过了不一会儿你就会产生疑问，因为你大问题上懂了，但不明白为啥每个子问题都可以这么用呢？每个子问题内为什么也起作用呢？
所以说之前的我和现在的我差在了哪里，不是智商，而是思考的方式不对！！你是不是正在苦苦思考这段代码的每一步，然后把一步步的执行过程都写出来了，想搞懂递归呢？结果就是蛋疼！你不但啥也没搞懂，还白白浪费了这段推代码的时间！正确的打开方式是这样的——递归当然只能以递归的思路理解，把它展开纯属自讨苦吃。
递归思路，说白了是如下三步：
1.对于问题N，如果N-1已经解决了，那么N是否很容易解决。
举例来说，如果要把一个N层汉诺塔从src搬到dst，那么：
如果前N-1层可以找别人搞定，咱只管搬第N层，会不会变得非常容易？
你看，这一下就简单了：这时当它只有两层就好了，先把前N-1层看作一个整体，把它搬到aux；然后把最下面的第N层搬到dst；然后再把前N-1层从aux搬到dst。
类似的，假如接到“搬前N-1层”这个任务的是我们，怎么搬呢？
简单，像前东家一样，把前N-2层外包出去，我们只搬第N-1层——其实和前面讨论过的“外包N-1层，只搬第N层”完全一样嘛。
依此类推，一层层“外包”下去——我不管你们有多伤脑筋，反正只要你们把我外包给你的活干了，我就能干了我的活！
这一步就是*递推。
注意这里的搬法：搬第N层，就需要把前N-1层搬两次(起始到辅助，辅助再到目标)，另外再把第N层搬一次(起始到目标)；
搬第N-1层，又需要把前N-2层搬两次，然后再把N-1层搬一次，依此类推。
an=2*a(n-1)+1
a(n-1)=2*a(n-2)+1
……
a2=2*a1+1
a1=1
很容易知道，an需要搬2^n-1次。
2、一步步递推下去，终究会有个“包工头”，接到“搬第一层”的任务。
第一层怎么搬？
太简单了，让搬哪搬哪。
换句话说，到此，递推就到了极限，简单粗暴直接做就可以了。
3.既然第一层搬了，那么第二层当然就可以搬了；第二层搬了，第三层又可以搬了……依次类推，直到第N层。于是问题搞定。
这一步就是回归。
如上三步加起来，就是递归。
推而广之，任何问题，不管规模为N时有多复杂，只要把N-1那块“外包”给别人做之后，我们在这个基础上可以轻易完成N，那么它很可能就适合用“递归”解决。
那么，怎么最终确定它能不能用“递归”做呢？
看当N取1或2之类最简情况时，问题是否可以解决——然后写程序解决它。
容易看出，“递归”其实和“数学归纳法”的思路非常像：证明N=1时成立；证明若N=n-1成立，则N=n时也成立；如上两步得证，则命题在n>1时一定成立（n为自然数）。你看，我们没必要从1开始逐一验证每个自然数，只要证明了“基础条件”、再证明了“递推条件”，大自然的规律会帮我们搞定一切。
换句话说，只要我们：
1、写程序告诉电脑“如何分解一个问题”(即把汉诺塔问题分解为如上三步)
2、写程序告诉电脑“当该问题分解到最简时如何处理”(即第二步中的直接把它从src移到dst)
那么，“具体如何递推、如何回归”这个简单问题就不要再操心了，电脑自己能搞定。
——写出问题分解方法、写出分解到最简后如何解决，这是我们的任务；把问题搞定，是电脑的任务。这就是递归的魅力。
正是由于这种“我提供思路你搞定细节”的特点，“一切皆递归”的函数系语言才被称为“声明式编程”（而不是必须一步一步指导电脑如何做的“命令式编程”）。