引子
有一款古老的游戏，它的名字相信很多人，特别是计算机相关专业的朋友都耳熟能详 －－汉诺塔。
这款游戏的基本玩法是这样的，得到几个大小不一的盘子，从大到小把它们摞成一个小塔，然后我们要把这座“小塔”移到目标位置去。
说完了游戏目标，我们再来说一说游戏规则。它的规则只有两个：第一，一次只能移动一个盘。第二，我们可以通过一个位置辅助的这个过程。
没听明白？没关系，我们看看下面的图。
两个盘子的玩法
最后，游戏的竞赛标准是，移动盘子次数最少达成目标就可以获胜。
想想古人没有iPad，没有PSP，没有小霸王，憋出这些游戏的点子也是蛮辛苦的。
正片
现在我们已经从简单的示例中知道，假如有两个盘子，那么最少的移动次数是三次。那么，如果有三个盘子呢？大家有兴趣可以自己试试，反正我是移了十多次😂。 同样，如果有四个盘子、五个盘子呢？
结果这个游戏就被数学家拿来当经典问题了，于是每一本算法书或者算法相关书都把这个游戏当做某一章节的例子... 这个万恶的章节就是递归
不知到计算机相关专业的同学是怎么看的，反正每次算法老师讲到这个例子，或者自己读到这个例子的时候...我！都！会！睡！着！
俗话说晕车的人开车才不会晕，那我自己来解释一波这个东东以免睡着，快上车！
把一头大象放进冰箱就算多么复杂，从理论上来讲，就三个步骤：
-
打开冰箱门。
-
把大象塞进去。
-
关上冰箱门。
Just joke~ 回到我们的问题，把一叠盘子移到目标位，也可以简化成三步：
1. 把最底下大盘子以上的盘子全部移到辅助位上。
2. 把最大的盘子移到目标位上。
3. 把辅助位上的一堆盘子移到目标位的大盘子上，完成了～
(靠，要是能移动一堆盘子还用你来讲？给我下车！)
且慢！给我个机会...
刚刚说的三个步骤看似违反规则，但是仔细想想，是不是在哪里见过？对的，在引子中，我们讲到了两个盘子的玩法，这三个步骤和两个盘子的玩法其实是如出一辙的。也就是说，如果我们能把最底下盘子之上的一堆盘子也拆解成这种三步节奏，那我们就能在不违反规则的情况下达到目的。
讲到这里，我顺便给大家安利一下递归的思想。
递归的基本定义是一个函数或者方法调用自身。那么啥时候调用的终点呢？这就引出了递归的一个特点：函数内必须有一个条件判断来终止递归
然后我们回到汉诺塔问题，先把这个处理问题的方法叫做hanoi。用这个方法处理问题，我们需要四个信息：盘子的个数(disc)、初始位(src)、辅助位(aux)、目标位(dst)。使用一次hanoi(disc, src, aux, dst)。我们就可以解决两个盘移到目标位的问题。
接下来，我们来定义这个函数
function hanoi ( disc, src, aux, dst ) {
hanoi (disc-1, src, dst, aux );
//第一步
//把盘数-1个盘子(除最底下的大盘)移到辅助位
//注意到参数的变化，我们把把辅助位当作目标点，目标点当作辅助位
console.log('Move disc' + disc +' from ' + src + ' to ' + dst );
//第二步
//把大盘子移到目标位
hanoi (disc-1, aux, src, dst);
//第三步
//把盘数-1个盘子)移到辅助位
//注意到参数的变化，我们把把辅助位当作起始位，起始位当作辅助位
}
我们可以看到，我们定义的方法内部使用方法本身去完成某些步骤。而这些函数的使用又会调用本身去完成它内部的某些步骤。这是一种特殊的分治策略。而分治的关键在于强调调用动作，而不强调内部细节。
但是不论如何，函数是应该计算出结果的，也就是说递归调用是应该有头的。就汉诺塔问题来讲，当需要移动的盘数为0（也就是说盘子都已经在目标位上了），我们就应该停止函数继续调用自己。
于是我们完善一下hanoi函数。给它加一个判断条件。
function hanoi ( disc, src, aux, dst ) {
if(disc === 0) {
return; //终止本次调用
}
hanoi (disc-1, src, dst, aux );
console.log('Move disc' + disc +' from ' + src + ' to ' + dst );
hanoi (disc-1, aux, src, dst);
}
然后我们就可以使用函数了，当我们有三个盘子的时候，我们这样用:
hanoi (3, 'Src', 'Aux', 'Dst');
程序打印出:
Move disc 1 from Src to Dst
Move disc 2 from Src to Aux
Move disc 1 from Dst to Aux
Move disc 3 from Src to Dst
Move disc 1 from Aux to Src
Move disc 2 from Aux to Dst
Move disc 1 from Src to Dst
算一算3个盘子最少移动次数才7次，楼主简直被程序完爆了T_T
思考
递归之所以绕，是因为它的特点完全和人类的顺序思维方式相反，一般来说，执行一个命令－得到结果－再执行一个命令，是我们比较舒服的思维方式。而递归的特质是它调用自己后不立即执行出结果，而是继续调用自己，直到遇到终止条件的时候，最后一个被调用的函数才开始执行结果，然后一层一层往回执行结果，最后一次得到的是最开始调用的函数的结果。就好比你对一个山谷喊话，第听到一声回音不是你最开始喊出的，而是你最后一次喊出的，怎能不觉得绕呢？
然而瑕不掩瑜，将一个庞大的问题拆解成可以分治的小问题，用短短几行代码高效地完成复杂的任务，这样的递归，如何能让人不着迷呢？
网友评论