汉塔算法用到递归算法（你会玩汉诺塔吗）

今天我们来介绍一种很常见的算法——递归。

什么是递归？简单的说，递归就是通过不断调用自己，来完成不断循环的一个过程。

可能概念有些拗口，我们编写一个递归函数来说明。斐波那契数列大家都知道，它从第三项开始，每一项都是前面两项的和：

1,1,2,3,5,8,13,21......

我们就用递归的思想来实现上面这个数列。

我们假设递归函数为f(x)，在编写递归函数时，要注意两点。

一是给定基本情况，这里的基本情况就是f(1)=1，f(2)=1。

二是确定规则，这里的规则就是f(x)=f(x-1) f(x-2)。

好了，现在我们可以进行函数的编写了：

OK，大功告成！是不是感觉很简单呢？我们来简单分析一下上面的代码：

首先，定义了一个函数叫f(x)。def是define的缩写，意思就是定义。f(x)中的x是项数，表示第几项，比如我们想知道斐波那契数列的第5项是什么，那么x=5。

其次，由于f(1)和f(2)的值都是1，可以把它们合并成x<=2的条件，返回1。

最后，当x>2的时候，返回的就是前两项的和，此时的f(x-1)和f(x-2)才有意义。

可能说了这么多，你还是会有疑问，那么我们就来举个实例来看下上述代码的运行过程吧。

比如我们想知道f(5)的值，因为5>2，因此返回前两项的和f(4) f(3)。

那f(4)和f(3)又分别等于多少呢？先来看f(3)，因为3>2，因此返回f(2) f(1)=1 1=2；再来看f(4)，因为4>2，因此返回f(3) f(2)=[f(2) f(1)] f(2)=1 1 1=3。

因此，f(5)=f(4) f(3)=3 2=5。调用我们编写的函数来验证一下：

我们再来看一个递归的实际应用——汉诺塔游戏。

如上图所示，有3跟杆子A、B、C，其中A上有大小不一的3个圆环，越在下面的圆环越大。我们的目标是，按照现在的顺序把3个圆盘从A挪到C。其中，有2个规则限制：

1.每次只能移动一个圆盘。

2.大的圆盘不能放在小的圆盘上面。

我们先从简单的情况看起吧，假如只有1个圆盘，那很容易，直接把圆盘从A移到C即可。

那2个圆盘的情况呢？我们画个图来说明：

如上图，有1、2两个圆盘，要想把2号圆盘移到C，那么首先需要移动1号圆盘。那1号移到哪里合适呢？很容易看出，1号移到B，那么下一步2号就可以直接移到C；如果1号移到C，那么2号还需要先到B再到C。因此，最快的方法是把1移动到B。

然后，我们就可以把2号圆盘移动到C。

最后，只需要把1号圆盘从B移到C即可。

好，我们来总结一下2个圆盘时的移动步骤。总共需要3步：第1步，把小圆盘从A移到B；第二步，把大圆盘从A移到C；第三步，把小圆盘从B移到C。我们要牢记这3个步骤，这是之后推理的基础。

接下来，我们就来看3个圆盘的情况。

我们来思考一下，要想把3个圆盘从A移到C，首先需要把3号上面的圆盘1和2移到B，这样3号才能直接到C。

关键的时刻来了，我们把1、2两个圆盘移到B，不就是我们之前讨论的2个圆盘的情况吗？只不过之前的目标是从A移到C，现在是从A移到B，同样是2个空着的杆子，仅仅是编号有差别，本质没有任何区别！

理解了上面的核心内容，我们的思路就变得清晰了。3个圆盘同样可以认为是3大步：第1步，把1和2移到B；第2步，把3移到C；第3步，把1和2从B移到C。而其中1和2如何移到B或者C，就是我们之前讨论的2个圆盘的情况了，这也就是递归的思想。

把上面的例子再拓展一下，如果是n个圆盘呢？

如上图，A上有n个圆盘，我们要把它按这个顺序移到C上。

就跟把大象关进冰箱需要3步一样，我们这个也只需要3步：第1步，把A中从1到n-1个圆盘移到B；第2步，把A中剩下的第n个圆盘移到C；第3步，把B中的n-1个圆盘移到C。至于如何把n-1个圆盘移到B，那就相当于重复我们上面的步骤，直到递归到我们熟悉的2个或3个圆盘所需的移动步骤。

好了，这就是今天的全部内容，欢迎留言讨论。