你会玩汉诺塔吗?——让递归算法来帮你,只需“3步”
今天我们来介绍一种很常见的算法——递归。
递归函数
什么是递归?简单的说,递归就是通过不断调用自己,来完成不断循环的一个过程。
可能概念有些拗口,我们编写一个递归函数来说明。斐波那契数列大家都知道,它从第三项开始,每一项都是前面两项的和:
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个圆盘所需的移动步骤。
好了,这就是今天的全部内容,欢迎留言讨论。